[백준] DP - 2225번, 합분해(다른 풀이 봄)

* 공부 목표

DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052

문) 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

입) 첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.

출) 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

---

풀이

1. 테이블 정의

• dp[k][n] = k개의 수를 더해 n을 만들 수 있는 경우의 수

 

2. 점화식

0~N까지의 숫자가 K개 주어진다는 상황을 가정해보자.

N = 마지막 값 + 이전 값들의 누적

점화식으로 적으면, DP[k][n] = DP[k-1][0] + .. + DP[k-1][n] 이다.

 

k (하단) / n	0	1	2	3
1	dp[1][0] = 1	dp[1][1] = 1	dp[1][2] = 1	dp[1][3] = 1
2	dp[2][0] = 1	dp[2][1] = 2	dp[2][2] = 3	dp[2][3] = 4
3	dp[3][0] = 1	dp[3][1] = 3	dp[3][2] = 6	dp[3][3] = 10

 

위의 내용을 코드로 바꾸면 3중 for문으로 작성하게 된다.

더 나은 방식이 없을까?

있다.

 

위의 표 내용을 자세히 보자.

기존의 생각이 전체 값을 더한다는 것이었다면,

이제는 필요한 값만 더해온다는 관점으로 바라보자.

 

dp[2][2]를 2가지로 표현해 볼 것이다.

1) dp[1][0] + dp[1][1] + dp[1][2]

k (하단) / n	0	1	2	3
1	1	1	1	1
2	1	2	3	4
3	1	3	6	10

기존 관점과 동일하다. 표시한 파란색 값을 다 더해야 빨간색 값이 나온다.

 

2) dp[2][1] + dp[1][2]

k (하단) / n	0	1	2	3
1	1	1	1	1
2	1	2	3	4
3	1	3	6	10

 

dp[2][1] = dp[1][0] + dp[1][1]

그러므로, dp[2][2] = dp[2][1] + dp[1][2] 로 대체하여 표현할 수 있는 것이다.

 

따라서 최종 점화식은 다음과 같다.

dp[k][n] = dp[k-1][n] + dp[k][n-1]

 

 

3. 초기값

• n = 0, dp[k][n] = 1 →dp[k][0] = 1
• k = 1, dp[k][n] = 1 →dp[1][n] = 1

 

코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[][] dp = new int[k+1][n+1];

        for(int i=0; i<k+1; i++) {
            dp[i][1] = i;
        }
        for(int i=0; i<n+1; i++) {
            dp[1][i] = 1;
        }
        for(int i=2; i<k+1; i++) {
            for(int j=2; j<n+1; j++) {
                dp[i][j] = (dp[i-1][j] + dp[i][j-1])% 1000000000;
            }
        }
        br.close();
        bw.write(String.valueOf(dp[k][n]));
        bw.flush();
        bw.close();
    }
}

---

파도반 수열 문제 풀고, 아 이제 좀 성장했나 싶었는데 바로 막혔다.

난이도 보니까 골드Ⅴ 문제였다. 흑.

열심히 해야겠다는 다짐을 오늘도 한다.

 

작다고만 생각말고 작은 생각을 매일 키워라.

 

 

[참고] https://hongjw1938.tistory.com/63  (풀이 정말 좋다!)

https://computer-choco.tistory.com/545  (위의 내용을 이해시켜주는 좋은 풀이!)