태그 보관물: 76

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

동전 100개를 나누는 방법

원문: 오일러 프로젝트 78번

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

동전 5개를 나누는 방법은 총 7가지가 존재한다.

ooooo
oooo o
ooo oo
ooo o o
oo oo o
oo o o o
o o o o o

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

동전을 나누는 문제는 동전더미의 수를 숫자로 치환하면

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

의 문제로 치환되며 이는 결국 영국화폐조합1의 문제로 귀결된다. 즉 동전의 종류가 5, 4, 3, 2, 1 일 때 이 동전들을 조합하여 5를 만드는 문제이다.

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만으로 나눠떨어지는 시점을 계산해야 한다는 점이다. 한계값을 알 수 없기 때문에 좀 골치아픈 문제인데…

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

뭐 이렇게 해놓고 마냥 기다리는 방법도 있긴하다만…

일단 최대치를 1000 정도로 잡고 돌려보면, (물론 그 안에 답은 없다) 이것마저도 상당한 시간이 걸린다. (약 37초) 왜? 동적 프로그래밍의 특성상 n보다 작은 케이스부터 차례대로 계산하기 때문에 n이 커지면 커질수록 계산시간이 지수적으로 증가하기 때문이다.

한 번에 계산하려면? 동적 프로그래밍으로 충분히 큰 값까지 계산하면 계산 과정 내에 충분히 큰 수 M 보다 작은 숫자들의 경우의 수가 모두 계산되기 때문에 구할 수 있을 법하지만, 그 ‘충분히 큰 값’을 예측하기가 어렵다.

그렇다면 한계치를 두지 않고 기존 계산값을 계속 유지하면서 사용하는 방법은 없을까?

동적 프로그래밍에 의해 값을 계산하는 과정을 추적해보면, 모종의 규칙을 발견할지도 모를일이다.

룰은 다음과 같다.

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

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

초기 값은 이런 형태가 된다. 그리고 한 번씩 이동해나가면…

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

이렇게 되어 p(1) = 1 이 나온다. 계속해보자.

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 .... ?

이번에는 2를 쓰느냐 안쓰느냐의 경우들을 더하는 것이므로 각 인덱스보다 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   3 .... ?
            1   1   2   3
                1   1   2
                    1   1
                        1

그래서 p(4) = 4, p(5) = 7, p(6) = 11 이 나오게 된다. 자 그럼 이 값에서 p(7)을 계산할 수 있을까?

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[] 의 각 항이 단일 정수값이 아니라 리스트라면?

p[n] = [ p[n-1][:2], p[n-2][:3], p[n-3][:4] ... p[0][:n]] 의 합이 된다. 물론 이 때 p[m] 의 길이가 n-k 보다 작으면 리스트 전체로 하면 된다.

그럼 계산 과정의 수열들을 보존하고, 이를 바탕으로 다음번 항을 계산하게 하기 위해서는 클래스를 하나 디자인하면 되겠다.

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까지의 값을 완벽하게 구해준다. 만세!…

그런데 느리다… 너무 느리다…. 이걸로는 답을 구할 때까지 얼마나 걸릴지 알 수가 없다. 튜닝을 해보지만 그 결과 역시 마뜩찮다.

각 단위를 계산할 때 백만 이하의 값만 사용한다 : 실제로 긴 정수 연산은 (파이썬에서는 매우 빠르긴하지만) 꽤 시간이 걸릴 수 있는 작업이다. 따라서 백만으로 나눈 나머지만 사용하여 0인지를 체크하도록 한다. 이 튜닝은 특정 값까지 도달할 때까지의 시간을 많이 단축하는 효과는 있지만, 정답은 수십만에서 수백만 단위에 있으리라 짐작되기 때문에 큰 효과는 없다.

분할수에 관련된 정리

특정 수를 다른 수의 합으로 표시하는 것을 분할 수라 하는데, 오각수정리라는 걸 살펴보니 분할수의 일반항은 다음과 같은 점화식으로 구성되더라.

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

와 같이 계산하며 일반항은 다음과 같이 정리된다.

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

이 때 \(g_{k}\)는 k 번째 오각수가 되며 이 k는 1, -1, 2, -2, 3, -3… 의 순서로 증가한다.

따라서 k 번째 오각수는 다음과 같이 정의한 함수를 통해서 얻을 수 있다.

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 번까지만 루트를 돌지만 무한루프를 돌면서 조건을 만족할 때까지 계속 항을 찾아나가보자. 또한 연산 속도를 빠르게 하기 위해서 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)

실행해보니 13초만에 답이 나온다. pypy로 돌렸을 땐 0.5초대에 답의 나왔다.

역시 pypy는 사랑입니다.