[C] LeetCode 264. Ugly Number II

 

문제

번역

ugly number는 소인수를 2,3,5만 갖고 있는 양수를 말한다.

정수 n이 주어졌을 때, n번째 ugly number를 반환해라.

접근 방법 및 소스 코드

처음엔 기존 ugly number를 구하는 코드를 그대로 활용하여 n번째 ugly number를 구했다.

 

int dp[1691];

bool isUgly(int n) {
    while(n%2==0) n/=2;
    while(n%3==0) n/=3;
    while(n%5==0) n/=5;
    return n==1;
}

int nthUglyNumber(int n) {
    dp[0] = 0; dp[1]=1;
    dp[2]=2; dp[3]=3; dp[4]=4;
    int i=5,j=5;
    while(i <= n) {
        if(isUgly(j)) {
            dp[i] = j;
            i++;
        }
        j++;
    }
    return dp[n];
}

 

이렇게 작성하고 제출하니 timeout이 발생했다.

그래서 힌트를 참고하니 대부분의 수는 ugly number가 아니기에 ugly number를 만드는 방법을 생각해보라 했다.

 

ugly number는 소인수 2,3,5로만 이루어져 있다.

그럼 다음 ugly number는 기존 ugly number에서 2,3,5를 곱한 것 중 가장 작은 것일 것이다.

2,3,5를 곱할 이전 값 포인터를 3개를 만들어두고 각 포인터에 2,3,5를 곱해서 가장 작은 값을 쓰면 된다.

 

int dp[1691];
int min(int a, int b, int c) {
    a = (a < b) ? a: b;
    a = (a < c) ? a: c;
    return a;
}

int nthUglyNumber(int n) {
    dp[0] = 0; dp[1]=1;
    int p2=1, p3=1, p5=1;
    for(int i=2; i<=n;i++) {
        dp[i] = min(dp[p2]*2, dp[p3]*3, dp[p5]*5);
        if(dp[p2]*2 == dp[i]) p2++;
        if(dp[p3]*3 == dp[i]) p3++;
        if(dp[p5]*5 == dp[i]) p5++;
    }
    return dp[n];
}

 

 

꽤나 괜찮은 결과가 나왔다.