#76 합의 경우의 수(Dynamic Programming)

이번 문제는 경우의 수를 계산하는 것입니다.  보통 분할(partition) 문제는 중복조합, 조합, 순열 등의 기법이 사용될 수 있지만, 이 문제와 같은 경우에는 분할이 쉽지 않습니다.

 

Combination with repetition

 

문제는 짧은 편입니다.

N이란 숫자가 주어지면, 1부터  N-1 까지의 숫자중 2개 이상을 선택해서 그 합이 N이 되도록 하는 경우의 수를 찾는 것입니다.

예를 들어서 N=5라고 한다면,

\( 5 = 1 + 1 + 1 + 1 + 1 \)

\( 5 = 1 + 1 + 1 + 2 \)

\( 5 = 1 + 1 + 3 \)

\( 5 = 1 + 4 \)

\( 5 = 1 + 2 +2 \)

\( 5 = 2+ 3 \)

위와 같이 총 6가지가 나옵니다.  

이 문제에서는 N=100일 때의 경우의 수가 얼마인지 계산하라는 문제입니다.

 

문제의 원본입니다.

https://projecteuler.net/problem=76

Problem 76 - Project Euler

사실 N의 수가 적기 때문에 모든 경우의 수를 따져도 많은 시간이 걸리지 않습니다.  제 노트북에서는 7초정도가 나옵니다.

 

#define N 100
int GetCaseCount(int remain, int v)
{
  if(remain == 0) return 1;
  if(remain < v) v = remain;
  int sum = 0;
  while(v) { sum += GetCaseCount(remain-v, v); v--; }
  return sum;
}
void solve1()
{
  printf("Ans = %d\n", GetCaseCount(N, N-1));
}

 

아주 평범한 알고리즘으로 작성했습니다.  이렇게 하나씩 경우의 수를 따지는 알고리즘 평가는 \( O(a^N) \) 입니다.  50개정도를 했을 때 5ms 정도인데 비해, 100개는 훨씬 경우의 수가 많아지니까요.  

작은 N에 대해서 해답을 적어보면 다음과 같습니다.

N	Answer
5	6
11	55
13	100
16	230
22	1001
27	3009
30	4564
50	204225

 

이 문제를 풀기 위해서는 동적 프로그래밍을 이용합니다.  1부터 k까지의 숫자만을 이용한 해답을 \(dp_k(N)\) 라고 한다면, \(dp_k(N)\) 는 다음과 같이 계산할 수 있습니다.

 

\[ dp_k(N) = dp_{k-1}(N) + \sum_{i=1}^{\lfloor (N-1)/k \rfloor} dp_{k-1}(N-ik) + u(N-k-1) \]

 

1 부터 k-1 까지의 숫자만을 이용한 해답과, 1부터 k-1까지의 숫자만을 이용한 해답중 k를 여러번 더해서 N이 되는 해답들의 합과 K보다 클 경우 1을 증가합니다.  마지막 1을 증가하는 것은 기존의 해답을 바탕으로 하지 않고, 1부터 k-1 수를 한번만 쓰고, 여기에 k를 여러번 더해서 N을 만드는 경우입니다.  이렇게 해서 해를 구하면, 수행시간이 0ms 수준으로 떨어집니다.

 

이런 방식으로 짠 소스는 다음과 같습니다.  소스는 참고용으로 봐주세요.

//--------------------------------------------------------------------
//  Project Euler #76 - Counting summations
//    - by Aubrey Choi
//    - created at 2015-10-09
//--------------------------------------------------------------------
#include <stdio.h>
#include <stdint.h>
#include <time.h>
#define  N  100

void solve2()
{
  int dp[N+1]={0,}, i, j, k;
  for(i=1;i<=N-1;i++)
  {
    for(j=N;j>i;j--) for(k=j-i;k>1;k-=i) dp[j]+=dp[k];
    for(j=i+1;j<=N;j++) dp[j]++;
  }
  printf("Ans = %d\n", dp[N]);
}
int main()
{
  clock_t t;
  t = clock();
  solve2();
  printf("Elapsed time is %.3f seconds \n", (float)(clock()-t)/CLOCKS_PER_SEC);
}