백준 13707, 합분해 2

개요

문제 링크
골드 4, DP
N을 K개의 수의 합으로 나타내는 방법의 수

---

접근

1. 조합론으로 풀 수도 있을텐데, DP는 Knapsack 생각하면 될 것 같다. 일단 N=5000이니까 O(N^3)은 안된다. 그럼 knapsack을 어떻게 O(N^2) 안에 해결하냐?

2. 개념적으로 접근해보자. N을 K개로 만드려면, [0,N]을 K-1개로 만든 경우를 모두 더해주면 된다. 그럼 2차원 dp를 활용해야 하나? 아니다. 굳이 쓰지 않고 1차원 dp 두개를 이용해 복붙해주면 된다.

3. 그럼 K번 돌리면서, N에 대해, n보다 작은 수의 k-1경우를 모두 더해주는 과정이다. 우선 for문 3개로 구현을 해보자.

   for (K)
       for (N)
           for (i = 0~n)
               sum += dp[i][k-1]
           dp[n][k] = sum

   O(N^3)이라 터진다. 이걸 해결하려면 누적합을 써주면 된다.

   // 2차원 -> 1차원
   for (K)
       sum[0] = 1
       for (N)
           sum[n] = sum[n-1]+dp[n]
           dp[n] = sum[n]

   이렇게 해주면 O(N^2)안에 문제를 해결할 수 있다. 우선 문제는 해결 됐는데, 사실 1차원 dp가 두개씩 필요한 것이 아니다. 하나로 줄이자.

   for (K)
       dp[0] = 1
       for (1~N)
           dp[n] += dp[n-1]

   이렇게 줄여도 정상적으로 작동한다.

---

Source code

#include <iostream>
using namespace std;

int R = 1e9;
int main() {
    int n, k;
    cin >> n >> k;
    int dp[n+1]={};

    while (k--) {
        dp[0] = 1;
        for (int i=1; i<=n; i++) {
            dp[i] += dp[i-1];
            dp[i] %= R;
        }
    }
    cout << dp[n];
}