[백준/BOJ/JAVA] 2225 합분해

 

 

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

덧셈의 순서가 바뀐 경우는 다른 경우로 센다. (즉, 하나의 수가 여러번 등장할 수 있다.)

 

N=3, K=3인 경우로 예시를 들어보자면

---

1. N=1일때

• K=1인경우 : 1가지 (1) 
• K=2인경우 : 2가지 (1+0, 0+1) 
• K=3인경우 : 3가지 (0+1+1, 1+0+1, 1+1+0) 

2. N=2일때

• K=1인경우 : 1가지 (2) 
• K=2인경우 : 3가지 (2+0, 0+2, 1+1) 
• K=3인경우 : 6가지 (2+0+0, 0+2+0, 0+0+2, 0+1+1, 1+0+1, 1+1+0) 

2. N=3일때

• K=1인경우 : 1가지 (3) 
• K=2인경우 : 4가지 (2+1, 1+2, 3+0, 0+3) 
• K=3인경우 : 10가지 (3+0+0, 0+3+0, 0+0+3, 1+1+1, 2+0+1, 1+0+2, 0+1+2, 0+2+1, 1+2+0, 2+1+0)

---

위와 같이 정리할 수 있다.

이것을 2차원 배열로 아래와 같이 정리할 수 있다.

 

1	2	3
1	3	6
1	4	10

 

아주 흔한.. DP[i][j-1] + DP[i-1][j] 형태가 된다.

이후엔 코드를 보면 이해가 빠르다!!!

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class BOJ_2225 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int[][] dp = new int[N][K];
 
        //1행 1열
        for(int i=1; i<=K; i++){
            dp[0][i-1] += i;
        }
 
        for(int i=1; i<N; i++){
            for(int j=0; j<K; j++){
                if(j==0)
                    dp[i][j] = 1;
                else
                    dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % 1000000000;
            }
        }
 
        System.out.println(dp[N-1][K-1]);
    }
}