어글리 넘버 Ugly Numbers

문제

어떤 수를 소인수분해 했을 때 그 소인수가 2 또는 3 또는 5로만 이루어진 수를 Ugly Number라고 부릅니다. Ugly Number를 차례대로 적어보면 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15... 입니다. 숫자 1은 Ugly Number의 첫 번째 수로 합니다. 자연수 N이 주어지면 Ugly Number를 차례로 적을 때 N번째 Ugly Number를 구하는 프로그램을 작성하시오.

 

해결

어글리 넘버는 2^x * 3^y * 5^z 로 표현할 수 있다.

즉, 어떤 어글리 넘버에 2 혹은 3 혹은 5를 곱한 값 또한 어글리 넘버이다.

따라서 어글리 넘버를 구하는 함수 f(x)에 대해서 f(0) = 1일때, f(n) = f(m)*2 혹은 f(m)*3 혹은 f(m)*5 이고, 이때 n > m이다.

하지만 m = n-1은 아니다. 가장 가까운 반례를 들자면 f(2) = 3인데 f(3) = 4 이기 때문이다.

 

아래 방식이 최선의 방식인지는 잘 모르겠지만 나름대로 풀어본 방법을 정리해보았다.

 

어글리 넘버를 작은 순서대로 벡터에 저장한다고 가정하자.

첫 번째 어글리 넘버는 1이다.

그리고 두 번째 어글리 넘버는 이전 어글리 넘버에 2 혹은 3 혹은 5를 곱한 값일 것이다.

어글리 넘버가 저장되는 벡터와 다음 어글리 넘버가 될 후보군을 표로 표현하면 다음과 같다.

후보군 표와 같이 vector[1] 는 vector[0]*2 = 2, vector[0]*3 = 3, vector[0]*5 = 5 중 최소값, 즉 2이다.

따라서 vector[1]에 2를 넣고, 후보군 표에서 2를 제거한다.

이제 새로운 어글리 넘버가 추가되었기 때문에, 어글리 넘버의 *2, *3, *5 또한 어글리 넘버라는 규칙에 따라 후보군에도 새 어글리 넘버들을 추가해 주어야 한다.

다음 어글리 넘버 vector[2]는 후보군 표의 5개 숫자 중 최소값이 될 것이다.

이때 후보군 표를 보고 알 수 있는 것이 있다.

vector[0]*3이 아직 후보군에 남아있기 때문에 vector[1]*3값을 최소값 후보로 고려하지 않아도 된다는 것이다.

(n > m 일 때 vector[n] > vector[m] 이 성립하기 때문이다)

같은 원리로 vector[1]*5 또한 후보군에서 제외된다.

하지만 vector[0]*2은 사용되었기 때문에, vector[1]*2는 후보군에 들어간다.

따라서 남아있는 후보군은 4, 3, 5 이다.

4, 3, 5 중 가장 작은 숫자는 3이므로, vector[2] 자리에 3을 넣고, 후보군 표에 vector[2]*2, vector[2]*3, vector[2]*5를 추가한다.

하지만 위와 같은 원리로, vector[1]*2이 남아있기 때문에 vector[2]*2은 후보군에서 제외된다. vector[2]*3과 vector[2]*5 또한 후보군에서 제외된다.

반대로 vector[0]*3이 사라졌기 때문에, 다음 후보로 vector[1]*3가 다시 추가된다.

따라서 남아있는 후보군은 4, 6, 5 이다.

남아있는 후보군 중 최소값은 4이므로, vector[3] 자리에 4를 넣고, 후보군 표에 vector[3]*2, vector[3]*3, vector[3]*5를 추가한다.

vector[1]*2가 사용되었으므로 vector[2]*2가 후보군에 추가되고, 방금 추가된 vector[3]*2, vector[3]*3, vector[3]*5는 후보군에서 제외된다.

남아있는 후보군은 6, 6, 5 이다.

남아있는 후보군 중 최소값은 5이므로, vector[4] 자리에 5를 넣고, 후보군 표에 vector[4]*2, vector[4]*3, vector[4]*5를 추가한다.

vector[0]*5가 사용되었으므로 vector[1]*5가 후보군에 추가되고, 방금 추가된 vector[4]*2, vector[4]*3, vector[4]*5는 후보군에서 제외된다.

남아있는 후보군은 6, 6, 10이다.

남아있는 후보군 중 최소값은 6이다.

이때 주의해야 할 점은 후보군에 최소값이 여러 군데서 나올 경우, 같은 값을 가진 후보를 전부 제거해주어야 한다는 점이다. 그렇지 않으면 다음 뽑기에서 또 6이 추가되어버린다.

vector[5] 자리에 6을 넣고, 후보군 표에 vector[5]*2, vector[5]*3, vector[5]*5를 추가한다.

vector[2]*2와 vector[1]*3이 사용되었으므로 vector[3]*2와 vector[2]*3이 후보군에 추가되고, 방금 추가된 vector[5]*2, vector[5]*3, vector[5]*5는 후보군에서 제외된다.

남아있는 후보군은 8, 9, 10이다.

 

위 과정을 통해 어글리 넘버를 구하는 과정에서 vector의 index값이 세 개(각각 *2, *3, *5를 하는데 사용된다) 필요하다는 것을 알 수 있다.

즉 코드로는 다음과 같이 구현할 수 있다.

1. index2 = index3 = index5 = 0 에서 시작한다.

2. vector[index2]*2와 vector[index2]*3과 vector[index5]*5를 비교한다.

3. vector[index2]*2가 최소값이 되어 어글리 넘버로 사용되었으므로 index2에 1을 더한다.

4. 다시 2 과정을 반복한다.

 

즉 후보 vector[indexn]*n 가 최소값이 되어 vector안으로 들어갔을 경우, 해당 indexn에 1을 더한 vector[indexn+1]*n 이 다음 후보에 추가되는 식으로 구현할 수 있다.

 

코드 구현

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	//몇 번째 어글리 넘버를 출력할 것인가를 입력받는다
    int nNumber = 0;
    cin >> nNumber;

    vector<int> vecUgly; //어글리 넘버가 들어갈 벡터
    int nIndex2, nIndex3, nIndex5; //*2, *3, *5가 사용할 각각의 인덱스
    nIndex2 = nIndex3 = nIndex5 = 0; //시작은 0부터

    vecUgly.push_back(1); //vector[0]은 1이다

    for (int i = 0; i < nNumber - 1; i++) //원하는 어글리 넘버가 나올 때까지 반복한다
    {
        int number1, number2, number3; //다음 어글리 넘버 후보군 셋
        
        //각 열(*2, *3, *5)의 후보들을 후보군에 넣는다
        number1 = 2 * vecUgly[nIndex2]; 
        number2 = 3 * vecUgly[nIndex3];
        number3 = 5 * vecUgly[nIndex5];

        int nMin; //후보들 중 최소값, 즉 다음 어글리 넘버

     	nMin = number1 < number2 ? number1 : number2; //후보1과 후보2를 비교해서 더 작은 값을 저장
     	nMin = nMin < number3 ? nMin : number3; //위에서 저장한 값과 후보3을 비교해서 더 작은 값이 최소값

        vecUgly.push_back(nMin); //발견한 최소값을 벡터에 넣는다

	//해당 인덱스를 사용한 값이 다음 어글리 넘버가 되었다면, 
        //인덱스에 +1을 해서 다음 후보를 후보군에 추가해준다
        //이때 else if를 사용하면 6, 6, 10 상황처럼 중복된 값이 있을 때
        //두 군데 모두 제거해주지 못하기 때문에 주의
        if (nMin == number1)
            nIndex2++;
        if (nMin == number2)
            nIndex3++;
        if (nMin == number3)
            nIndex5++;
    }

    cout << vecUgly.back(); //마지막으로 넣어진 어글리 넘버를 출력한다
}

 

테스트

10번째 어글리 넘버는 12라고 한다. 1,2,3,4,5,6,8,9,10,12니까 맞는 것 같다.

1500번째 어글리 넘버는 859963392라고 한다. 확인할 수는 없지만 답지가 맞다고 하니 맞는 것 같다.