책 이야기

Let p(n) represent the number of different ways in which n coins can be separated into piles. For example, five coins can be separated into piles in exactly seven different ways, so p(5)=7.

    OOOOO
    OOOO   O
    OOO   OO
    OOO   O   O
    OO   OO   O
    OO   O   O   O
    O   O   O   O   O

Find the least value of n for which p(n) is divisible by one million.

n개의 동전을 서로 다른 방법으로 묶는 방법을 p(n)이라 하자. 예를 들어, 5개의 동전은 일곱 가지 다른 방법으로 묶을 수 있다. 따라서 p(5)=7이다.

    OOOOO
    OOOO   O
    OOO   OO
    OOO   O   O
    OO   OO   O
    OO   O   O   O
    O   O   O   O   O

p(n)이 1백만인 n의 최소값을 찾으시오.

--------------------------------------------------------------------------

동전으로 변형되어 있지만 문제 자체는 76번 문제과 동일한 알고리즘으로 해결 가능하다. 즉, 오일러의 오각수 정리 공식을 적용하면 된다. 76번과 차이점은, 76번은 2개 이상의 조합을 요구했기 때문에 전체 숫자에 해당하는 1을 빼야하지만(위 예시에서 동전 5개 묶음을 제외하므로 76번에서 p(5)=6), 이번 문제에서는 그 과정이 필요없다는 것이다.

한가지 고려할 사항은 동전 숫자에 상한선이 없으므로 76번 문제에서 적용했던 방법을 조금 변형시킬 필요가 있었다. 처음에는 상한선을 1만으로 했는데 답이 나오지 않아, 10만으로 바꾸고 나서 답을 구할 수 있었다.

It is possible to write five as a sum in exactly six different ways:

    4 + 1
    3 + 2
    3 + 1 + 1
    2 + 2 + 1
    2 + 1 + 1 + 1
    1 + 1 + 1 + 1 + 1

How many different ways can one hundred be written as a sum of at least two positive integers?

합계로 5를 나타내는 방법은 다음과 같이 6가지가 있다:

    4 + 1
    3 + 2
    3 + 1 + 1
    2 + 2 + 1
    2 + 1 + 1 + 1
    1 + 1 + 1 + 1 + 1

100을 2개 이상 숫자의 합으로 표시하는 데에는 몇가지 방법이 있는가?

--------------------------------------------------------------------------

예시를 제외하면 문제는 2줄 밖에 안되지만, 막상 구현하려 하면 간단한 것이 아니었다. 문제31의 변형이어서 그 때 사용한 방법을 적용하려 보니 31번에서는 8종류의 동전을 이용하는 8중 반복문을 이용해서 구현했는데, 이 문제는 그 경우 99종류의 동전이 있기 때문에 99중 반복문을 구현해야 가능한 것이었다. 그렇게 해결할 수도 있겠지만 문제에서 원하는 방법이 그것이 아니어서 고민을 많이 했는데 해결책이 떠오르지 않아 많이 애를 먹었다.

가장 간단하게 해결하는 것은 동적 프로그래밍을 이용하는 것인데, 다른 사람이 해결한 코드를 보면 간단하지만 왜 그렇게 답이 나오는지 이해가 되지 않아 많이 난감했다.

그래서 관련 내용을 추가로 찾아보니 이 문제는 정수론(number theory)이나 이산수학(Discrete Mathematics)에서 다루는 분할수(Partition Number) 문제라고 한다. 답을 구하는 방법으로 오일러의 오각수 정리, 하디-라마누잔-라데마커 공식과 같은 것이 있는데 오일러의 오각수 정리를 이용해서 답을 구했다. 위키피디아 보다는 나무위키의 분할수 항목에 프로그램으로 구현 가능하도록 공식이 나와 있어 그것을 이용했다.