[JAVA] 백준 2225번 : 합분해

 

---

 

• 코드

코드 설명 :

 

만약 입력에 5 3 가 주어졌다고 가정하면 우리는 이를 0+5, 1+4, 2+3, 3+2, 4+1, 5+0로나눌수있다.

 

0(2번 더해서 0이 되는 경우)+5(1번 더해서 5가 되는 경우)

1(2번 더해서 1이 되는 경우)+4(1번 더해서 4가 되는 경우)

2(2번 더해서 2이 되는 경우)+3(1번 더해서 3가 되는 경우)

3(2번 더해서 3이 되는 경우)+2(1번 더해서 2가 되는 경우)

4(2번 더해서 4이 되는 경우)+1(1번 더해서 1가 되는 경우)

5(2번 더해서 5이 되는 경우)+0(1번 더해서 0가 되는 경우)

 

즉, DP[2][5] = DP[1][0] + DP[1][1] + DP[1][2] + DP[1][3] + DP[1][4] + DP[1][5] 가 된다. 

 

K와 N으로 바꾸면 DP[K][N] = DP[K-1][0] + DP[K-1][1] + … + DP[K-1][N] 임을 알 수 있다.

 

풀어서 표로 확인해보면

표를 토대로 좀 더 간단하게 점화식을 세우면 DP[K][N] = DP[K][N-1] + DP[K-1][N-1]라는 것을 유추할 수 있다.

 

 

 

정답 코드 : 나온 DP[K][N] = DP[K][N-1] + DP[K-1][N-1] 식을 사용하여 구현 하였다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception {
		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[201][201];
		
		for(int i=1;i<=K;i++) {
			dp[i][0]=1;
		}
		for(int i=1;i<=K;i++) {
			for(int j=1;j<=N;j++) {
				dp[i][j] = dp[i][j-1] + dp[i-1][j];
			}
		}
		System.out.println(dp[K][N]%1000000000);
		
	}

}