[C/C++] 프로젝트 오일러 #113 Non-bouncy Numbers(수학)

Project Euler 문제 113번은 숫자가 “증가형(increasing)” 혹은 “감소형(decreasing)” 형태인 ‘비탄력적(non-bouncy)’ 수의 개수를 구하는 문제입니다. 이 문제의 핵심 개념을 다음과 같이 정리할 수 있습니다.

 

1. 증가하는 수(Increasing number): 왼쪽에서 오른쪽으로 읽을 때, 각 자리수가 이전 자리수보다 작아지지 않는(즉, 비내림(non-decreasing) 순서) 수를 말합니다. 예를 들어, 112233이나 8999는 모두 증가하는 수에 해당합니다.

 

2. 감소하는 수(Decreasing number): 왼쪽에서 오른쪽으로 읽을 때, 각 자리수가 이전 자리수보다 커지지 않는(즉, 비내림(non-increasing) 순서) 수를 의미합니다. 예를 들어, 3210이나 66550은 감소하는 수에 해당합니다.

 

3. 비탄력적 수(Non-bouncy number): 증가하는 수나 감소하는 수처럼 한 방향으로만 정렬된 수를 의미합니다. 반면, 이 두 조건 중 어떤 것도 만족하지 않는, 즉 오르내리는 패턴을 가지는 수를 탄력적(bouncy) 수라고 합니다.

이 문제는 자연수가 커질수록 탄력적 수의 비율이 급격히 증가한다는 사실을 바탕으로 합니다. 작은 자릿수의 수들 대부분은 증가하거나 감소하는 형태로 쉽게 분류되지만, 자릿수가 커질수록 대부분의 수는 탄력적인 형태로 변합니다. 그 결과, 매우 큰 수 중에서 비탄력적 수를 찾는 일은 점점 더 어려워집니다.

Project Euler #113 문제에서는 특정한 매우 큰 범위, 즉 \(10^{100}\)(구골, googol) 미만의 양의 정수들 중에서 비탄력적 수의 개수를 구하는 것을 목표로 합니다. 이는 단순한 계산 방식으로는 처리하기 불가능한 대규모 범위이므로, 조합론적 접근법, 동적 프로그래밍(DP) 기법 또는 수학적 성질을 활용해야 하는 문제입니다.

정리하자면, Project Euler #113 문제는 비탄력적 수의 정의와 성질을 이해한 뒤, \(10^{100}\) 미만의 양의 정수 중 비탄력적 수가 몇 개인지를 효율적으로 계산하는 난제라고 할 수 있습니다.

 

non-bouncy numbers

 

제가 문제를 풀기 위해 작성한 소스입니다.

//------------------------------------------------
//    Project Euler #113 - Non-bouncy Numbers
//        - by Aubrey Choi
//        - created at 2015-04-02
//------------------------------------------------
#include <stdio.h>
#include <stdint.h>

uint64_t comb(int n, int r);
int main()
{
    uint64_t sum = 0;
    printf("%ju %ju\n", comb(10, 2), comb(11, 2));
    for( int i = 1 ; i <= 100 ; i++ )
    {
        sum += comb(9+i-1, i) + comb(10+i-1, i) - 10;
    }
    printf("Ans = %ju\n", sum);
}

uint64_t comb(int n, int r)
{
    uint64_t m = 1;
    if( 2*r > n ) r = n-r;

    for( int i = 1 ; i <= r ; i++ )
    {
        m *= n--;
        m /= i;
    }
    return m;
}

 

전체적인 동작 원리는 다음과 같습니다.

코드 개요
• comb(n, r) 함수를 통해 조합 값을 계산합니다. 이 함수는 nCr(이항 계수, 조합 수)를 효율적으로 구하는 기능을 담당합니다.
• 메인 함수에서는 1자리 수부터 100자리 수까지 각각에 대해 증가하는 수, 감소하는 수의 개수를 조합론적으로 계산한 뒤 더해줍니다.
• 문제에서 요구하는 비탄력적 수(증가하거나 감소하는 수)의 합을 구한 뒤 출력합니다.

코드 상세 설명
1. 헤더 파일 포함 및 타입 정의

#include <stdio.h>
#include <stdint.h>

• <stdio.h>는 입출력 함수 사용을 위해, <stdint.h>는 uint64_t와 같은 고정폭 정수 타입 사용을 위해 포함하였습니다.
• uint64_t는 64비트 부호 없는 정수형으로, 매우 큰 범위의 수를 다룰 때(특히 조합 계산 시) 오버플로우를 방지하기 위함입니다.

2. comb 함수: 이항 계수(조합) 계산

uint64_t comb(int n, int r)
{
    uint64_t m = 1;
    if( 2*r > n ) r = n-r;

    for( int i = 1 ; i <= r ; i++ )
    {
        m *= n--;
        m /= i;
    }
    return m;
}

• comb(n, r)는 n개 중에서 r개를 뽑는 조합(이항 계수) nCr을 계산합니다.
• if (2*r > n) r = n-r;는 대칭성을 이용하여 r을 더 작은 값으로 치환함으로써 계산 시간을 줄이는 전형적인 기법입니다. (nCr = nC(n-r))
• 반복문 내에서 m에 순차적으로 분자와 분모를 나누어 최종 조합 값을 계산합니다. 정수 나눗셈 과정에서 정확한 조합 값을 얻기 위해 분자에 곱한 뒤 바로 분자로 나누는 방식을 사용합니다.
• 결과적으로 m는 nCr의 값이 됩니다.

3. main 함수 상세

int main()
{
    uint64_t sum = 0;
    printf("%ju %ju\n", comb(10, 2), comb(11, 2));
    for( int i = 1 ; i <= 100 ; i++ )
    {
        sum += comb(9+i-1, i) + comb(10+i-1, i) - 10;
    }
    printf("Ans = %ju\n", sum);
}

• printf("%ju %ju\n", comb(10, 2), comb(11, 2));는 comb(10,2)와 comb(11,2)의 값을 출력합니다. 이는 디버그나 검증용 출력으로 추측됩니다.
• for (int i = 1; i <= 100; i++) 반복문 안에서 sum을 계산하는 식이 이 문제의 핵심 로직입니다.
• comb(9+i-1, i)는 증가하는 i자리 수의 개수를 계산하는 조합 공식에서 사용됩니다.
• 증가하는 수의 개수는 ‘중복 조합(multichoose)’를 활용하면 구할 수 있습니다.
• i자리 증가하는 수의 개수는 C(9+i, i) 형태의 조합으로 표현할 수 있는데, 여기서는 인덱스를 약간 변형해 comb(9+i-1, i)로 계산하고 있습니다. C(n+r-1, r) 형태로 중복 조합을 구하는 전형적 공식입니다.
• comb(10+i-1, i)는 감소하는 i자리 수의 개수를 계산하는 식입니다.
• 감소하는 수의 개수 역시 비슷한 조합 개념을 이용하지만, 감소하는 수에는 0을 허용하는지 여부에 따라 공식이 약간 달라질 수 있습니다.
• 여기서는 C(10+i-1, i) 형태로 계산하고 있습니다.
• -10을 하는 이유는 증가하는 수와 감소하는 수를 모두 더했을 때, ‘중복’으로 세어지는 부분(예: 모든 자리가 동일한 수, 즉 증가도 감소도 되는 수)을 제거하기 위함입니다. 보통 한 자리씩 동일한 수(예: 1111)는 증가하는 수도 되고 감소하는 수도 됩니다. 이를 중복으로 계산하지 않기 위해 -10을 해주는데, 이는 각 자리수가 모두 같을 때(0~9), 총 10개가 중복 세어졌기 때문입니다.
• 최종적으로 sum은 1자리부터 100자리까지의 모든 비탄력적 수(증가하거나 감소하는 수)의 총합을 계산한 값이 됩니다.
• printf("Ans = %ju\n", sum);를 통해 해당 결과를 출력합니다.

정리
이 코드는 Project Euler #113 문제에서 요구하는 비탄력적 수의 개수를 효율적으로 계산하기 위한 조합론적 접근을 구현한 예시입니다. 조합 함수 comb(n, r)를 통해 각 자리수 길이에 따른 증가/감소 수의 개수를 구하고, 이 둘을 더한 뒤 중복된 경우(증가도 되고 감소도 되는 경우)를 제거하는 방식으로 최종 결과를 구합니다.