(백준 / DP / 중복 순열) 합분해

문제 요약

전형적인 DP 문제.

• 0~N까지의 정수 K개를 더해 합이 N이 되는 경우의 수를 구하라

원문

솔루션

• 중복 수열을 모두 돌면 \(200^{200}\) 이다.
• 상태 공간을 정의해서 중복연산이 일어나지 않게 해주어야한다.

상태공간

다이나믹 프로그래밍의 기본은, 이전에 탐색을 완료한 상태는 다시 연산하지 않는 것이다.

문제에서 원하는 결과값은 K개의 정수 합으로 N을 만드는 경우의 수 이다

K보다 작은 수 k가 잇고 N보다 작은 수 n이 있을 때, k개의 정수 합으로 n을 만드는 법을 안다면 다시 연산할 필요가 없다.

예를들어

3개의 수로 2개를 만드는 경우,

0 0 2

0 1 1

0 2 0

1 0 1

1 1 0

2 0 0

여섯 가지 수가 있으며 위에서부터 알수 있는 내용은 다음과 같다..

첫 번째, 1개의 숫자 합으로 2를 표현하는 경우의 수는 1개다.

두 번째, 1개의 숫자 합으로 1을 표현하는 경우의 수는 1개다.

세 번째, 1개의 숫자 합으로 0을 표현하는 경우의 수는 1개다.

첫 번째에서 세 번째, 2 개의 숫자 합으로 2를 표현하는 경우의 수는 1.와 2.와 3.의 합인 3이다.

네 번째는 1개의 숫자의 합으로 1을 나타내는 경우의 수를 요구하지만, 이는 두 번째에서 구한 값이므로 중복되는 연산이다.

다섯 번째는 1개의 숫자 합으로 0을 나타내는 경우의 수를 요구하지만, 이는 세 번째에서 구한 값이므로 중복되는 연산이다.

여섯 번째는 2개의 숫자 합으로 0을 나타내는 경우의 수를 요구하지만, 이는 세 번째에서 구한 값이므로 중복되는 연산이다.

시간복잡도

상태공간을 그림으로 그리면 트리모양이 나온다. 이는 단순하지만

트리구조를 DP 최적화 시켰을 때 시간복잡도는 아직까지 어떻게 나타내면 좋을지 모르겠다.

구현 순서

1. 정수의 범위 N과 정수의 개수K 입력,
2. r개의 숫자로 sum만큼 나타낸 상태를 정의하는 함수 작성
   1. 해당 상태를 방문한 적이 없는경우 재귀호출
   2. 방문한 적이 있는 경우 저장된 값 사용
   3. N개 숫자를 모두 사용했을 경우 숫자의 합에 따라 1아니면 0 반환

      코드

      ```c++ #include #include using namespace std; /* * N : 정수의 범위 * K : 정수의 개수 * DP[n][s] = n개의 수로 s를 만드는 경우의 수 */ int N, K; long long int DP[211][211] = { 0, }; //r : 사용한 수의 개수 //sum : r개의 수를 사용했을 때 남은 채워야할 수의 합 long long int f(int r, int sum) { long long int ret = 0, num = 0;

   if (r == K) { if (sum == 0) return 1; else return 0; }

   int i, j; for (i = 0; i <= sum; i++) { //방문한 적이 없는 경우 if (DP[r + 1][sum - i] == -1) { num += (f(r + 1, sum - i) % (long long int)1e9); } //방문 했던 경우 else num += (DP[r + 1][sum - i] % (long long int)1e9); } //탐색 결과를 저장 DP[r][sum] = num; return num; } int main() { cin » N » K; int i, j; for (i = 0; i <= 200; i++) { for (j = 0; j <= 200; j++) { DP[i][j] = -1; } } cout « f(0, N) % (long long int)1e9 « endl; return 0; } ```

이슈

• 1e9로 나누어 주지 않아 정수 범위를 초과해,,,
  • 자바스크립트와 파이썬에 익숙해지는 바람에 그만,,,