분할수 – 오일러프로젝트 078

동전 100개를 나누는 방법

이 문제는 오일러 프로젝트 76번 문제와 같은 문제로 볼 수 있는데…. 처음 작성한 시점부터 너무 오래된 글이라, 진도를 기다리지 못하고 미리 발행한다.

5개의 동전이 있다.  이 동전들을 나누는 방법을 생각해 보자. 동전 5개는 아래와 같이 총 7가지 방법으로 나눌 수 있다.

ooooo  # 5개짜리 그룹 1개
oooo o  # 4개 + 1개
ooo oo  # 3개 + 2개
ooo o o # 3개 + 1개 + 1개
oo oo o # 2개 + 2개 + 1개
oo o o o # 2개 + 1개 + 1개 + 1개
o o o o o # 1개 + 1개 + 1개 + 1개

이렇게 동전 n개를 나눌 때의 나누는 방법의 가짓수를 p(n)이라 할 때, p(n)이 백만으로 나누어 떨어지는 최소의 n은 얼마인가?

접근

동전을 나누는 문제에 대해서 나눠진 각 그룹을 해당 그룹의 동전수로 치환하면  n을 n이하의 자연수의 합으로 나타내는 가지수와 같은 문제가 된다. 따라서 위의 도식은 아래와 같이 표현할 수 있게 된다.

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

이는 동전의 종류가 1, 2, 3, 4, 5원이 있을 때 5원을 만드는 방법의 가지수와 동일하므로 결국 영국화폐조합1의 문제로 귀결된다. 따라서 n에 대해서 p(n)을 구하는 방법은 동적프로그래밍을 사용하여 풀 수 있고, 이는 아래의 코드로 표현할 수 있다.

def getWays(target):
    ways = [1] + [0] * target
    values = range(1, target+1)
    for value in values:
        for i in range(value, target+1):
            ways[i] += ways[i-value]
    return ways[-1]

print getWays(5)

문제는 이걸 가지고 값이 100만으로 나눠떨어지는 시점을 계산해야 한다는 점이다. n의 범위를 알 수 없기 때문에 좀 골치가 아픈 문제이다. 일단 무식하게 i = 2 부터 시작해서 1백만으로 나눠떨어지는 지점까지 찾아서 실행해보자.

i = 2
while True:
    w = getWays(i)
    if w % 1000000 == 0:
        print i, w
        break
    i += 1

뭐 이렇게 해놓고 마냥 기다렸을 때 언제 끝날지 모를 정도로 오래 걸린다. 동적 프로그래밍의 특성상 n에 대해서 P(n)을 구할 때는 재귀적인 방법들보다는 빠르게 계산할 수 있지만, 여기서는 n이 계속 바뀌기 때문이다. 따라서 n보다 작은 케이스부터 차례대로 계산하기 때문에 n이 커지면 커질수록 전체 계산시간은 지수적으로 증가하고, 이 루프에 있어서는 부분 문제를 중첩하는 방법을 찾기가 까다롭다.

찾을 수 있을지도 모르겠다. 이 부분은 더 고민이 필요할 듯 하다.

충분히 큰 수 M에 대해 계산한다면, M보다 작은 값 중에서 답이 있다면 오랜 시간이 걸리지 않을 수 있다. 하지만 M이 얼마가 될지 모르기 때문에 여기서 막히게 된다.

대안

그렇다면 작은 n에 대해서 P(n)을 계산해 나가면서 이전에 계산했던 값을 재활용할 수 있는 방법이 있는지 살펴보자. 어쨌거나 반복계산을 엄청나게 수행하는 것 보다는 이게 나을 것 같다. 동적 프로그래밍에 의해 값을 계산하는 과정을 추적해보면, 모종의 규칙을 발견하게 될지도 모르겠다.

이를 위해서 내가 세워본 룰은 다음과 같다.

  1. 각 n에 대해 가지수를 저장하는 배열 ways는 첫 원소가 1이고 나머지는 0으로 채워진 target + 1 만큼의 길이를 가지고 있다.
  2. 그리고 n 번째 항을 계산할 때는 n 보다 작은 자연수인 values의 각 value 값에 대해서 value 값 만큼 적은 인덱스의 값을 누적해서 더해주게 된다.

0   1   2   3   4   5   6 .... N
---------------------------------
1   0   0   0   0   0   0 .... 0

초기 값은 이런 형태가 된다. 자 그래서 1개짜리 그룹을 포함하는 경우는 각 n에 대해서 (n-1)번째의 현재값을 더한 것이 된다. 물론 이는 중간 과정이며, n=1,2,3… 의 순으로 각각 더해준다. 여기까지의 결과는 아래와 같고, 따라서 P(1) = 1 이 된다.

value: 1
0   1   2   3   4   5   6 .... N
---------------------------------
1   0   0   0   0   0   0 .... 0
    1   1   1   1   1   1 .... 1

계속해보자. 이번엔 2개짜리 그룹을 사용하느냐의 여부다. 이는 각 n에 대해서 (n-2)위치의 값을 더해주는 계산을 한다.  2의 맨 아래에는 0번의 값을 더했고, 4의 맨 아래에는 2에서 계산된 결과를 더했다.

value: 2
0   1   2   3   4   5   6 .... N
---------------------------------
1   0   0   0   0   0   0 .... 0
    1   1   1   1   1   1 .... 1
        1   1   2   2   2 .... ?

이제 P(2)=2로 계산됐다. 3부터 계속 채워나가 보자.

0   1   2   3   4   5   6 .... N
---------------------------------
1   0   0   0   0   0   0 .... 0
    1   1   1   1   1   1 .... 1
        1   1   2   2   3 .... ?
            1   1   2   3
                1   1   2
                    1   1
                        1

그래서 p(4) = 4, p(5) = 7, p(6) = 11 이 나오게 된다. (각 n에 대해서 해당 열의 세로로 나열된 숫자들의 합이 된다.) 그럼 이 값에서 p(7)을 계산할 수 있을까?  만약 아래와 같이 p(n)을 구하는 과정에서 총 합만을 남기는 것이 아니라, 모든 단계의 값을 분리해서 보관한다면 가능할 것 같다.

0   1   2   3   4   5   6 .... 7
---------------------------------
1   0   0   0   0   0   0 .... 0
    1   1   1   1   1   1 .... 1 --> p(6)중 0, 1 의 합
        1   1   2   2   3 .... 3 --> p(5)중 0, 1, 2 의 합 
            1   1   2   3 .... 4 --> p(4)중 0, 1, 2, 1 의 합
                1   1   2 .... 3 --> p(3)중 0, 1, 1, 1 의 합
                    1   1 .... 2 --> p(2)중 0, 1, 1 의 합
                        1 .... 1 --> p(1)중 0, 1의 합 
                               1 --> p(0)중 1의 합 

그렇다면 각 ways[n] 의 각 항이 단일 정수값이 아니라 리스트라면, p[n] = [ p[n-1][:2], p[n-2][:3], p[n-3][:4] ... p[0][:n]]  이 된다.

그럼 계산 과정의 수열들을 보존하고, 다음 항을 계산할 때 값을 추가해나가는 식으로 계산하는 코드를 짜보자.

class Dist(object):
    def __init__(self):
        self.n = 0
        self.ways = [[1]]

    def expand(self):
        self.n += 1
        self.ways.append([0])
        for value in range(1, self.n+1):
            self.ways[self.n].append(sum(self.ways[self.n-value][:value+1]))
        return sum(self.ways[self.n])

d = Dist()
for i in range(1, 11):
    print i, d.expand()

이를 실행해서 돌려보면 1~10 사이의 값에 대해서는 P(n)을 잘 구해준다. 하지만 이렇게 돌려서 구현한 목적은 “계산을 빠르게”하기 위한 것이었는데, n이 커지면 커질 수록 계산에는 여전히 많은 시간이 소요된다. (리스트에 대한 append 라든지 하는 부분들이 비용이 꽤나 큰 연산이다.) 실제로 계산해보면 이 방식도 너무나 느리다. 게다가 이 문제는 그 값 역시 엄청나게 커지기 때문에 큰 정수 연산이 들어가면서 계속 문제가 된다. 실제로는 백만으로 나눈 나머지만 확인하면 되기 때문에 백만 이상의 값은 버리도록 튜닝을 해 보아도 이렇게 풀어서는 답이 안나온다. 다른 접근법이 필요하다.

또다른 접근 : 분할수에 관련된 정리

특정 수를 다른 수의 합으로 표시하는 것을 분할수라고 한다. 분할수 관련해서 구글링을 해보면 오각수정리라는 것을 만날 수 있다. 이 정리는 보통 아래와 같은 수식으로 표현된다.

 p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + \cdots

이 때 1, 2, 5, 7은 오각수의 수열이며, 이 수열이 n보다 작을 때까지   P(n-k)들의 값을 더하거나 빼서  P(n)을 만들 수 있다는 것이다.  즉, 이를 정리하면 아래의 식이 된다.

 p(n) = \sum _{k} (-1)^{k-1}p(n-g_{k})  

이 때 g_{k}는 1, -1, 2, -2, 3, -3… 의 수열의 각 항을 이용해서 오각수 공식에 대입하여 얻은 수이다. 다음과 같이 정의한 함수를 통해서 얻을 수 있다.

def getPenta(k):
    # n: 1, -1, 2, -2, 3, -3 ...
    n = (k/2 + 1 if k % 2 == 0 else (k / 2)* -1 - 1)
    return n*(3*n - 1) / 2

이 수열은 다음과 같이 나온다.

1
2
5
7
12
15
22
26
35
40

그럼 이제 일반항을 구하는 생성함수를 보자.

 p[n] = p[n-1] + p[n-2] - p[n-5] - p[n-7] + p[n-12] ....

이런 식으로 이어지며, 이 때 p[0] = 1, p[음수] = 0 으로 처리된다. 즉 g_{k}가 n 보다 작아지는 상황이 오면 계산이 종료된다고 보면 된다. 또한 각 항의 부호는 +, +, -, – 의 패턴으로 반복된다. 따라서 일반항을 구하는 함수를 다시 써보면 아래와 같이 정리할 수 있다. (역시 동적계획법이지만 연산의 수가 훨씬 적다)

def getP(n):
    signs = (1, 1, -1, -1)
    p = [1] + [0] * n
    for k in range(1, n+1):
        pk = 0 # p[k]의 항이 될 값
        i = 0 # 점화식 내의 부분 수열의 인덱스
        penta = getPenta(i) # gk
        while penta <= k:
            pk += signs[i%4] * p[k-penta]
            i += 1
            penta = getPenta(i)
        p[k] = pk
    return p[-1]

최종장

이제 이 문제의 답 구하는 작업에 다시 도전해보도록 하자. 위의 함수는 n 번까지만 루트를 돌지만 무한루프를 돌면서 조건을 만족할 때까지 100만으로 나눠지는 항이 있는지 찾는다. . 또한 큰 정수 연산에 대한 부담을 줄여서 연산 속도를 빠르게 하기 위해서 p[k] 항에는 100만으로 나눈 나머지만 저장하도록 하겠다.

def main():
    signs = (1, 1, -1, -1)
    p = [1]
    while True:
        k = 1
        pk = 0
        i = 0
        penta = getPenta(i)
        while penta <= k:
            pk += signs[i%4] * p[k-penta]
            i += 1
            penta = getPenta(i)
        pk = pk % 1000000
        if pk == 0:
            print k
            return
        p.append(pk)

 

기대와 달리 엄청 빠르게 답이 나오지 않지만 (대략 10~13초 가량 소요된다) 그럼에도 불구하고 처음 몇 번의 시도에 비해서는 상당한 발전이다.