동전 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개를 나눌 때의 나누는 방법의 가짓수를 이라 할 때, 이 백만으로 나누어 떨어지는 최소의 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)을 계산해 나가면서 이전에 계산했던 값을 재활용할 수 있는 방법이 있는지 살펴보자. 어쨌거나 반복계산을 엄청나게 수행하는 것 보다는 이게 나을 것 같다. 동적 프로그래밍에 의해 값을 계산하는 과정을 추적해보면, 모종의 규칙을 발견하게 될지도 모르겠다.
이를 위해서 내가 세워본 룰은 다음과 같다.
- 각 n에 대해 가지수를 저장하는 배열 ways는 첫 원소가 1이고 나머지는 0으로 채워진
target + 1
만큼의 길이를 가지고 있다. - 그리고 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
<strong>1 1 1 1 1 1</strong> .... 1 --> p(6)중 0, 1 의 합
<strong>1 1 2 2</strong> 3 .... 3 --> p(5)중 0, 1, 2 의 합
<strong>1 1</strong> 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 라든지 하는 부분들이 비용이 꽤나 큰 연산이다.) 실제로 계산해보면 이 방식도 너무나 느리다. 게다가 이 문제는 그 값 역시 엄청나게 커지기 때문에 큰 정수 연산이 들어가면서 계속 문제가 된다. 실제로는 백만으로 나눈 나머지만 확인하면 되기 때문에 백만 이상의 값은 버리도록 튜닝을 해 보아도 이렇게 풀어서는 답이 안나온다. 다른 접근법이 필요하다.
또다른 접근 : 분할수에 관련된 정리
특정 수를 다른 수의 합으로 표시하는 것을 분할수라고 한다. 분할수 관련해서 구글링을 해보면 오각수정리라는 것을 만날 수 있다. 이 정리는 보통 아래와 같은 수식으로 표현된다.
이 때 1, 2, 5, 7은 오각수의 수열이며, 이 수열이 n보다 작을 때까지 P(n-k)들의 값을 더하거나 빼서 P(n)을 만들 수 있다는 것이다. 즉, 이를 정리하면 아래의 식이 된다.
이 때 는 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[0] = 1, p[음수] = 0 으로 처리된다. 즉 가 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초 가량 소요된다) 그럼에도 불구하고 처음 몇 번의 시도에 비해서는 상당한 발전이다.
- 오일러프로젝트 31번 문제 ↩