52. Ugly numbers

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다.

문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅

 

 

입력예제 1

10

 

출력예제 1

12

 

풀이 

-3 point 알고리즘

-소인수 분해해서 2, 3, 5로만 이루어진 수를 찾는다

- 3개의 포인터를 놓고 위치 값에 2, 3, 5로 곱하는데 이때 가장 작은 값으로 다음 값을 바꿔준다

- for문은 2번부터 n번까지, n번째 값이 정답이 된다

- 2, 3, 5로만 곱해진 수에 2, 3, 5를 곱하기 때문에 당연히 2, 3, 5 만으로 이루어진 수가 된다.

- 주의해야 할 점이 있는데 가장 작은 값이 p2, p3, p5에서 중복해서 나올 수 있다. 

=> 따라서 min값을 구하고 p2, p3, p5값 중 어떤 값이 min값에 해당하는 지 찾을 때 if문을 사용해 중복으로 ++ 가능하게 한다.

 

[EX]

1      

p2(1) X 2

p3(1) X 3

p5(1) X 5

(2,3,5) => 다음값 2, 포인터2++

 

2

p2(2) X 2 => 4

p3(1) X 3 => 3

p5(1) X 5 => 5

 

(4,3,5) => 다음값 3, 포인터3++

 

 

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int a[1501];

// 52. Ugly Numbers(3 point)
int main() {
    int n, i, p2, p3, p5, min=2147000000;
    scanf("%d",&n); //몇 번째 ugly number인지
    a[1]=1; //첫 번째 수는 1
    p2=p3=p5=1;
    
    for(i=2;i<=n;i++){
        if(a[p2]*2<a[p3]*3) min=a[p2]*2;
        else min=a[p3]*3;
        if(a[p5]*5<min) min=a[p5]*5; //둘 중에 min과 비교해서 작으면 min
        if(a[p2]*2==min) p2++; //p2가 min이면 ++
        if(a[p3]*3==min) p3++; //else if 아닌 이유는 동시에 min과 같은 값이면 둘 다 위치 이동
        if(a[p5]*5==min) p5++;
        a[i]=min;
    }
    
    printf("%d\n", a[n]);
    
    return 0;
}