[백준] 합분해

 

합분해(골 5) : https://www.acmicpc.net/problem/2225

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 문제.

즉, n = 3, k = 2가 주어지면,

(0, 3) (1, 2)  (2, 1) (3, 0)의 네 가지 경우의 수를 구할 수 있음.

 

---

 

1. 문제 분석

 

경우의 수를 모두 구하는 문제니, 최적화 문제는 아님.

for문 돌면서 k가 1씩 감소하면서 재귀 호출을 하면 될 것 같음!

 

2. 완전 탐색 구현

 

#include <iostream>

using namespace std;

int disassemble(int n, int k)
{
  if (k == 0)
  {
    if (n)
      return 0;
    return 1;
  }

  int cnt = 0;

  for (int num = 0; n + 1 > num; num++)
  {
    if (n - num < 0)
      continue;

    cnt += disassemble(n - num, k - 1) % 1000000000;
  }
  return cnt;
}

int main(void)
{
  int N, K;

  cin >> N;
  cin >> K;

  cout << disassemble(N, K) << '\n';

  return 0;
}

 

n과 k가 조금만 커져도, 재귀 중복호출이 많이 일어나고, 경우의 수 자체가 기하급수적으로 커진다. 따라서, int -> long long으로 바꾸고, DP화를 하여 시간을 단축시킬 수 있다.

 

 

3. DP화

 

메모리제이션 구현 레시피(https://sanghoonly.tistory.com/29)대로 DP화 완료!

 

#include <iostream>
#include <memory.h>

using namespace std;

long long cache[201][201];

long long disassemble(long long n, long long k)
{
  if (k == 0)
    return 1;

  long long &ret = cache[n][k];

  if (ret != -1)
    return ret;

  long long cnt = 0;

  for (long long num = 0; n + 1 > num; num++)
  {
    if (n - num < 0)
      continue;

    if (k - 1 == 0 && n - num != 0)
      continue;

    cnt += (disassemble(n - num, k - 1));
  }
  return ret = cnt % 1000000000;
}

int main(void)
{
  long long N, K;

  cin >> N;
  cin >> K;

  memset(cache, -1, sizeof(cache));

  cout << disassemble(N, K) << '\n';

  return 0;
}