[백준 02225] 합분해 [Java]

문제

2225번: 합분해

2225번: 합분해

 

---

풀이

정수 K개의 합이 N이 되도록 만드는 경우의 수를 세는 문제다.

덧셈의 순서가 바뀐 경우는 다른 경우이지만, 동일한 수에 대한 연산은 하나의 경우로 볼 수 있다.

ex) 1+2, 1+2는 다른 경우, 1+1, 1+1은 피연산자의 순서는 다르지만, 덧셈의 순서(?)는 다르다.

dp[N][K] : 정수 K로 N을 만드는 경우의 수

초기값부터 설정하자.

dp[0][K]인 경우 0만 가능하다.

        for (int k = 1; k <= K; ++k) {
            dp[0][k] = 1;
        }

dp[N][1]은 N자신만 가능하다.

        for (int i = 1; i <= N; ++i) {
            dp[i][1] = 1;
        }

dp[N][K]는 dp[N - 1][K]의 맨 뒤 요소를 1늘리는 경우와

dp[N][K-1]에 0을 추가해주는 경우로 볼 수 있다.

        for (int i = 1; i <= N; ++i) {
            for (int k = 2; k <= K; ++k) {
                dp[i][k] = (dp[i - 1][k] + dp[i][k - 1]) % MOD;
            }
        }

dp[3][2] = dp[2][2] + dp[3][1]을 예시로 설명하면 다음과 같다.

dp[2][2] = { (0, 2), (1, 1), (2, 0) }

→ { (0, 3), (1, 2), (2, 1) }

dp[3][1] = { (3) }

→ { (3, 0) }

따라서 dp[3][2] = { (0, 3), (1, 2), (2, 1), (3, 0) }가 된다.

풀이 시간

20분

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/normal/02225.java

problem-solving/baekjoon-online-judge/normal/02225.java at main · rogi-rogi/problem-solving