24. 프로젝트 오일러 #24 : 백만번째 순열 수 구하기

우리가 진법을 계산할 때, 과연 어떻게 할까요?

예를 들어서 723 을 8진법으로 계산한다면요?

이 계산을 위해서 우리는 나누기 연산을 계속 하게 됩니다.  중학교 수학을 들추어 보면 보통 다음과 같이 계산을 합니다.

으로 723은 8진수로 으로 표시가 됩니다.

이것을 수식으로 표현하면 다음과 같이 표현할 수 있습니다.

이야기는 우리는 8의 3승부터 차례로 나누어 나가서 몫만 챙겨도 똑같이 위와 같은 결론에 도달할 수 있다는 것을 의미합니다.

그런데, 순열은 다른 것이 아닌가요?

순열은 한번 사용된 글자는 사용할 수 없다는 것만 빼고는 위와 같습니다.  그런 이유 때문에, 진법계산을 할 때, 1의 자릿수부터 계산하는 것이 가능한 반면, 순열은 그렇지 못 합니다.  반드시 가장 큰 자리부터 계산해야 합니다.

예를 들어서 0, 1, 2 로 순열을 생성한다면,

012, 021, 102, 120, 201, 210

으로 총 6가지가 나옵니다.

앞에서 사용한 숫자는 사용할 수 없다는 것만 빼고 진법 계산과 같다고 했습니다.  그러다 보니, 3의 몇승 형태가 아니라 팩토리얼로 표시가 되어야 합니다.  4번째 숫자는 얼마일까요라고 한다면, 3이란 숫자를 가지고 시작합니다.  (진법에서 첫번째 숫자는 0이듯이 여기서도 마찬가지입니다.)

팩토리얼은 다음과 같이 값을 얻을 수 있습니다.

0! = 1

1! = 1

2! = 2

3! = 6

..

3은 위 숫자 중 3!로는 나눌 수 없고, 2!로 나눌 수가 있죠.  나머지는 1이 됩니다.  그래서 다음과 같은 숫자를 얻을 수 있습니다.

이 식을 통하면, 첫번째 숫자가 1이므로 우리는 2번째 숫자를 택합니다.  2번째 숫자는 1입니다.  그 다음 숫자 역시 1이므로 첫번째 선택한 숫자를 제외한 두번째 숫자를 선택합니다.  그 값은 2입니다.  마지막 숫자는 0이므로 첫번째와 두번째에서 사용된 숫자를 제외한 숫자 중 첫번째 숫자를 선택합니다.  그래서 0이 됩니다.

그래서 순열에서 얻은 4번째 숫자는 120이 됩니다.

처음 0, 1, 2로 생성한 순열에서 4번째 값을 보면, 120이 맞는 것을 알 수 있습니다.

이렇게 알고리즘을 정하면, 백만번째 순열 수를 구하기 위해서 일일이 순열을 생성할 필요가 없습니다.  그냥 각 자릿수의 값을 구하면 됩니다.

참고로, 제가 올린 소스는 참고용, 공부용으로만 써주세요.

#include <stdio.h>
#include <memory.h>

int main()
{
    int f = 3628800;
    int n = 1000000;
    int v[10];

    memset(v, 0, sizeof(v));

    n--;

    printf("Ans = ");
    for( int i = 10 ; i >= 1 ; i-- )
    {
        f /= i;
        int c = n/f;
        n = n%f;
        for( int j = 0 ; j < 10 ; j++ )
        {
            if( v[j] == 0 )
            {
                if( c == 0 ) { v[j] = 1; putchar('0'+j); break; }
                c--;
            }
        }
    }
    putchar('\n');
}