#78 코인 나누기(Dynamic Programming)

코인 나누기는 유명한 문제 중 하나입니다.  동적 프로그래밍을 이용해서 구할 수 있는데, 그것을 하기 위해서는 수학적 기반 지식이 있어야 합니다.

 

코인 나누기라는 것은 N개의 코인을 가지고 코인 갯수를 나누는 방법의 수를 구하는 것입니다.  또는 무한정의 1$, 2$, 3$, .., N$ 코인으로 N$를 만드는 방법의 수라고 할 수도 있습니다.

 

예를 들어서 코인이 5개 있다면, 아래의 그림과 같이 7가지 방법으로 나눌 수 있습니다.

 

Coin Partitions

문제에서 요구하는 것은 이 경우의 수가 1,000,000으로 나누어 떨어지는 가장 적은 수를 구하라는 문제입니다.  단순하게 N에 대해서 경우의 수를 구하는 문제였다면 크게 어렵지 않았을겁니다.  난이도가 30%로 설정된 이유도 아마 비슷할 것이라고 봅니다.

 

수학적으로 본다면 다음과 같이 표현할 수 있습니다.  N개의 코인 나누는 방법의 수를 $p(N)$ 이라고 한다면,

 

$$p(n)=0,\text{if}n<0$$

$$p(0)=1$$

$$p(n)=\sum _{k=1}^{\mathrm{\infty }}(-1{)}^{k+1}(p(n-k(3k-1)/2)+p(n-k(3k+1)/2))$$

 

n의 길이에 따라서 나눌 수 있는 방법의 수를 따져보면 다음과 같습니다.

n	cases	solutions
1	1	(1)
2	2	(1,1)(2)
3	3	(1,1,1)(1,2)(3)
4	5	(1,1,1,1)(1,1,2)(1,3)(2,2)(4)
5	7	(1,1,1,1,1)(1,1,1,2)(1,1,3)(1,2,2)(1,4)(2,3)(5)

 

기본적으로 이 문제를 풀려면, 1부터 차례대로 숫자를 증가시키면서 동적 프로그래밍으로 해를 구하는 것입니다.

 

$$p(0)=1$$

$$\text{for}k=1\text{to}n,p_k(n)=\sum _{s=0}^{\mathrm{\infty }}{p}_{k-1}(n-sk)$$

 

이 방법을 이용하면, $O(n^3)$의 성능이 나옵니다.  하지만 위의 공식을 이용하면, $O(n\sqrt{n})$ 정도의 시간이면 해결이 가능합니다.  수학적으로 도출하는 것은 전문 수학자가 아닌 이상 힘들지만, OEIS 등을 참조하면 공식을 얻을 수가 있습니다.  그리고 이번 문제와 같이 한계가 명확하지 않은 문제의 경우라면 이 방법을 적용하는 것이 쉽지 않습니다.

 

제가 작성한 소스 코드입니다.

 

//--------------------------------------------------------------------
//  Project Euler #78 - Coin Partitions
//    - by Aubrey Choi
//    - created at 2015-04-12
//--------------------------------------------------------------------
#include <stdio.h>
#define  LIMIT  100000
#define  MOD    1000000

//  p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + ...
//  p(n) = sum_{k=1}^{infty} (-1)^{k+1}((p(n-k(3k-1)/2) + p(n-k(3k+1)/2)))
unsigned dp[LIMIT+1];
int main()
{
  int n, s, i, m;
  dp[0] = 1;
  for( n = 1 ; n <= LIMIT ; n++ )
  {
    for( i = 1, s=0 ;  ; i++ )
    {
      if((m = n-i*(3*i-1)/2) < 0) break;
      s += (i%2)?dp[m]:MOD-dp[m];
      if((m = n-i*(3*i+1)/2) < 0) break;
      s += (i%2)?dp[m]:MOD-dp[m];
      s %= MOD;
    }
    dp[n] = s%MOD;
    if( dp[n] == 0 )
    {
      printf("ans = %d\n", n);
      break;
    }
  }
}