동전을 여러 더미로 나누는 경우의 수 세기
생각을 정리해 두는 것이 좋을 것 같아서 써봅니다. ^^
*** 유의사항: "프로젝트 오일러의 76, 78번 문제"를 풀지 않은 분들의 경우 가능한 문제를 풀고 나서 읽기를 바랍니다.
사실 76번과 78번 문제는 같은 유형의 문제입니다.
Problem 76 (숫자 100을 두 개 이상의 자연수의 합으로 나타내는 방법은 모두 몇 가지
; http://euler.synap.co.kr/prob_detail.php?id=76
Problem 78 (동전을 여러 더미로 나누는 경우의 수 세기)
; http://euler.synap.co.kr/prob_detail.php?id=78
우선, 각 동전별로 나올 수 있는 경우의 수를 성능을 고려하지 않은 코드를 이용해서 출력을 해 보니 다음과 같은 결과를 얻을 수 있었습니다.
3 ==> 2가지
2,1
1,1,1
4 ==> 4가지
2,1,1
1,1,1,1
3,1
2,2
5 ==> 6가지
2,1,1,1
1,1,1,1,1
3,1,1
2,2,1
4,1
3,2
6 ==> 10가지
2,1,1,1,1
1,1,1,1,1,1
3,1,1,1
2,2,1,1
4,1,1
3,2,1
5,1
4,2
2,2,2,
3,3,
7 ==> 14가지
2,1,1,1,1,1
1,1,1,1,1,1,1
3,1,1,1,1
2,2,1,1,1
4,1,1,1
3,2,1,1
5,1,1
4,2,1
2,2,2,1
3,3,1
1,6
2,5,
2,2,3,
3,4,
잘 보면, 일정한 규칙이 나오는데 딱 3가지로 정리해 볼 수 있습니다.
1. n의 숫자에서는 n - 1의 경우의 수를 모두 포함
예를 들어, 3의 경우에 "2,1", "1,1,1"을 포함하는데, 4에서는 3이 가지고 있는 경우의 수에 "+1"만 하는 모든 경우의 수가 포함됩니다.
4 ==> 4가지
2,1,1
1,1,1,1
3,1
2,2
2. 2자리 수의 합이 n이 되는 경우의 수가 새롭게 추가됨.
4의 경우에 새롭게 "3 + 1", "2 + 2"이 추가되는 것을 볼 수 있습니다. 중복되는 경우의 수가 나오면 안되기 때문에 다음과 같이 절반만 루프를 돌아주면 됩니다.
for (int t = 1; t <= i / 2; t++)
{
배열 { i - t, t } 추가
}
3. 이전 수로부터 물려받은 3자리 이상의 배열에서 가장 마지막 2자리 수의 차가 1 이상인 경우 마지막 자리에 +1을 한 경우의 수를 추가
말이 좀 긴데요. 예를 들어, 숫자 6에 대한 경우의 수가 5로부터 물려받은 수는 다음과 같습니다.
2,1,1,1 <== 마지막 2자리 수의 차가 0
1,1,1,1,1 <== 마지막 2자리 수의 차가 0
3,1,1 <== 마지막 2자리 수의 차가 0
2,2,1 <== 마지막 2자리 수의 차가 1 이상
4,1 <== 2자리 수
3,2 <== 2자리 수
따라서, 조건을 만족하는 배열이 "2,2,1"이므로, 이런 배열을 만나면 마지막 자리 수에 +1을 해서 추가를 해주면 됩니다. 위의 상황에서는 "2,2,2" 배열이 추가되는 것입니다.
그래서, 처음에는 이전 배열 목록을 만들어서 누적시켜 나가는 방향으로 코드를 만들어서 결과를 내려고 했는데요. 아쉽게도 답까지 가지 못했습니다. ^^; 문제는 메모리! 제 노트북 메모리가 8GB인데 금방 소진을 하고 엄청난 하드 디스크 스와핑 현상이 발생하면서 시간 지연이 너무 길어서 중도에 포기를 했습니다.
어쩔 수 없이 메모리 소비를 줄이는 아이디어를 내야 했는데... 다행히 2가지 정도의 방안이 떠 올랐습니다.
1. 이전 경우의 수에 대해서는 누적 숫자만 보관하고 메모리에서 제거
예를 들어, 4의 경우의 수와 5의 경우의 수를 비교해 보면,
4 ==> 4가지
2,1,1
1,1,1,1
3,1
2,2
5 ==> 6가지
2,1,1,1
1,1,1,1,1
3,1,1
2,2,1
4,1
3,2
달라지는 것이라고는 그저 "1"만 추가되는 것일 뿐 사실상 메모리에 들고 있을 필요가 없습니다. 게다가 연이어서 5의 경우의 수가 6으로 넘어가도 모든 것들에 "+1"만 되는 것일 뿐이어서 굳이 보관할 필요가 없어서 제거 대상이 될 수 있습니다.
2. 모든 경우의 수를 보관할 필요 없이 최대 마지막 3자리 수만 보관하면 됨.
숫자도 모든 수를 보관할 필요는 없습니다. 이전 수가 가진 배열에서 판단이 필요한 것은 "3번 조건"으로 "이전 수로부터 물려받은 3자리 이상의 배열에서 가장 마지막 2자리 수의 차가 1 이상인 경우 마지막 자리에 +1을 한 경우의 수를 추가"하기 위해서는 "3자리 이상의 배열" 값인 것만 알면 됩니다. 그래서, 이전 배열로부터 물려받은 것 중 마지막 2자리 숫자의 차가 1 이상인 배열만 물려받고 그중에서도 3자리 수만 보관하고 있으면 됩니다.
이렇게 해도 소비 메모리가 약 18GB에 달해서 하드 스와핑이 발생합니다. 하지만 ^^ 이번 경우에는 저도 더 이상의 방법이 없다고 생각하고 데스크톱에서 테스트를 하여 결과를 냈는데 시간도 16분이 걸렸습니다.
성능 좋은 데스크톱을 이용하여 넘어간 꼼수는 ^^; 아쉽게도 오래가지 못했습니다. 문제는 78번에서 걸린 것입니다. 겨우 숫자 100에 해당하는 76번의 답을 내는 수준에서도 메모리가 18GB를 넘는데 78번의 답에서는 영영 답이 안 나올지도 모른다는 생각이 들었습니다. ^^ 어쩔 수 없이 지난번 생각에 대해 개선이 필요했는데요.
다시 뚫어지게 경우의 수를 쳐다봤습니다. ^^
그랬더니... 오호~~~ 보이기 시작합니다. 이번엔 이전 배열의 수에 대해 보관을 하지 않고도 가능한 방법이 나타났습니다.
1. (n - 1)의 누적값은 숫자로만 보관
이에 대해선 이미 이전에 설명했기 때문에 생략합니다. 어쨌든 배열을 보관하지 않아도 된다는 것이 중요합니다.
2. 두자리 숫자의 합에 대한 경우의 수도 계산 가능
숫자리 숫자의 합은 "((n / 2) - 1)"이라는 간단한 공식으로 표현이 되어서 그 부분에 대한 루프도 생략이 가능했습니다.
3. n번째 배열의 경우의 수에 영향을 주는 이전 배열의 경우의 수에 대한 결과만 보관
숫자 6의 경우를 보면 다음과 같이 구성된 것을 볼 수 있습니다.
[5의 경우의 수를 포함]
2,1,1,1,1
1,1,1,1,1,1
3,1,1,1
2,2,1,1
4,1,1
3,2,1
5,1 <= 2자리 숫자의 합 (1)
4,2 <= 2자리 숫자의 합 (2)
2,2,2,
3,3, <= 2자리 숫자의 합 (3)
여기서, "2,2,2"가 어디서 왔는지를 판단해야 하는데, 이것은 2자리 숫자의 합 중에서 "2 + 4"에 힌트가 있습니다. 4의 구성요소를 보면, 다음과 같은데요.
2,1,1
1,1,1,1
3,1 <= 2자리 숫자의 합 (1)
2,2 <= 2자리 숫자의 합 (2)
보시는 것처럼, 6의 경우의 수에서 "2 + 4"의 조합에서 "4"에 대한 경우의 수를 이어받게 되어 있습니다. 그런데, 4에 대한 모든 경우의 수를 이어받는 것이 아니고, 6의 2자리 숫자의 합의 순서와 일치하는 4의 2자리 숫자의 합에 대한 경우의 수를 가져옵니다. (정확하게는 누적값을 가져오게 되는데, 이에 대해서는 좀 더 설명이 필요하지만 장황해지므로 생략합니다. 차근차근히 보면 누적 규칙을 어렵지 않게 발견할 수 있습니다. ^^)
결과는 아주 만족스럽습니다. 위와 같이 해주면 이전의 알고리즘으로 메모리 18GB에 16분이나 걸렸던 작업이 메모리 소비 거의 없이 10ms도 체 안되는 시간에 숫자 100에 대한 경우의 수를 계산해 냅니다.
그런데, 여전히 78번 문제에서는 위의 알고리즘도 문제가 되었습니다. 1백만으로 나눠 떨어지는 경우의 수를 찾아야 하는데, 숫자 100에 대한 경우의 수에서도 1억이 넘어가 버리는 바람에 숫자가 너무 커져 버려서 부득이 BigInteger를 써야만 정상적인 합이 나올 정도로 숫자가 커져갔습니다.
어느 정도냐면??? 숫자 14574에 대한 경우의 수가 "3023230991908581568928363906501639271939935875772000955326621702587696794760453659405017864587829790913886891883621070101089120000" 로 나왔으며 그 순간에 메모리는 1.5GB까지 소비되어 있었습니다. 그야말로 '헉'소리 나오는데요. ^^;
78번 문제를 풀기 위해서는 뭔가 개선이 필요하다는 생각이 다시 들었습니다. 음... 그러다 한 가지 묘책이 떠오르더군요. ^^ 어차피 1백만으로 나눠서 떨어지면 되기 때문에 모든 숫자를 보관할 필요 없이 백만 이상의 값은 잘라 버리고 보관을 하는 식으로 바꾸고 그래서 BigInteger 값이 아닌 보통의 int 값으로 자료구조를 바꿀 수 있었고, 이로 인해 메모리가 약 4.0GB 소비로 바뀌고 376초만에 결과를 냈습니다.
일단, 여기까지 해서 76번/78번에 대한 제 탐구는 끝이 났고 답을 낸 다음에 "
Project Euler"에서 다른 이들이 답을 쓴 것을 보았습니다. 오호~~~ 점화식을 이용해서 풀었는데요. 코드를 보니, 마법같은 점화식 변수가 하나 나옵니다. 수학에 대한 깊이가 없는 저로써는 도저히 알아낼 수가 없는 ^^ 식이더군요. 저 역시 나름대로 76번 문제를 풀면서 숫자가 점진적으로 증가하는 것에 대해 무언가 점화식을 추론할 수 있지 않을까 싶었는데, 생각만 했을 뿐 발견해낼 수가 없었습니다. 점화식 답을 보고 나서... 추론하는 데 시간을 보내지 않기를 잘했다는 생각이 들더군요. ^^;
어쨌든... 문제를 풀다보니 재미있는 것들을 많이 알게 됩니다. ^^ 게다가 역시, 수학을 알고 모르고의 차이가 분명히 있다는 것도 알게 되었고.
참고로, 76번의 경우 답을 제외하고 99번까지의 단계별 경우의 수는 다음과 같습니다. ^^ 문제 푸는 분들께 도움되길 바랍니다.
3 ==> 2
4 ==> 4
5 ==> 6
6 ==> 10
7 ==> 14
8 ==> 21
9 ==> 29
10 ==> 41
11 ==> 55
12 ==> 76
13 ==> 100
14 ==> 134
15 ==> 175
16 ==> 230
17 ==> 296
18 ==> 384
19 ==> 489
20 ==> 626
21 ==> 791
22 ==> 1001
23 ==> 1254
24 ==> 1574
25 ==> 1957
26 ==> 2435
27 ==> 3009
28 ==> 3717
29 ==> 4564
30 ==> 5603
31 ==> 6841
32 ==> 8348
33 ==> 10142
34 ==> 12309
35 ==> 14882
36 ==> 17976
37 ==> 21636
38 ==> 26014
39 ==> 31184
40 ==> 37337
41 ==> 44582
42 ==> 53173
43 ==> 63260
44 ==> 75174
45 ==> 89133
46 ==> 105557
47 ==> 124753
48 ==> 147272
49 ==> 173524
50 ==> 204225
51 ==> 239942
52 ==> 281588
53 ==> 329930
54 ==> 386154
55 ==> 451275
56 ==> 526822
57 ==> 614153
58 ==> 715219
59 ==> 831819
60 ==> 966466
61 ==> 1121504
62 ==> 1300155
63 ==> 1505498
64 ==> 1741629
65 ==> 2012557
66 ==> 2323519
67 ==> 2679688
68 ==> 3087734
69 ==> 3554344
70 ==> 4087967
71 ==> 4697204
72 ==> 5392782
73 ==> 6185688
74 ==> 7089499
75 ==> 8118263
76 ==> 9289090
77 ==> 10619862
78 ==> 12132163
79 ==> 13848649
80 ==> 15796475
81 ==> 18004326
82 ==> 20506254
83 ==> 23338468
84 ==> 26543659
85 ==> 30167356
86 ==> 34262961
87 ==> 38887672
88 ==> 44108108
89 ==> 49995924
90 ==> 56634172
91 ==> 64112358
92 ==> 72533806
93 ==> 82010176
94 ==> 92669719
95 ==> 104651418
96 ==> 118114303
97 ==> 133230929
98 ==> 150198135
99 ==> 169229874
[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]