[JAVA] 백준 2225번 : 합분해

2225번: 합분해

 

문제

- 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램

- 덧셈의 순서가 바뀐 경우 다른 경우로 셈(1+2와 2+1은 다른경우)

- 한 개의 수를 여러번 쓸 수 있다.

 

입력

첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)

 

출력

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

 

 

풀이

만약 입력에 5, 3가 주어졌다고 가정했을 때, 생각할 수 있는 경우의 수는 아래와 같다.

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

 

우리가 구해야 하는 경우의 수를 DP[K][N]이라고 하면,

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

 

즉, 점화식으로 표현한다면 DP[K][N] = DP[K-1][0] + DP[K-1][1] + … + DP[K-1][N] 일 것이다.

 

좀 더 알기 쉽게 표로 나타내면

이런 식인데 보다보면 계속 반복되는 합을 이용하는 걸 알 수 있다.

K=1, N=0인 경우를 제외하면, DP[K][N]에 대하여 아래의 식을 나타낼 수 있다.

 

DP[K][N] = DP[K][N-1] + DP[K-1][N] 

 

이 점화식을 이용하여 코드를 작성하면 아래와 같다.

 

public class bj2225 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner s = new Scanner(System.in);
		int n = s.nextInt(); // n 입력받음
		int k = s.nextInt(); // k 입력받음
		
		int[][] dp = new int[201][201]; // k번 더해서 n이 되는 경우의 수
		
		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])%1000000000; // 1000000000으로 나누는 걸 출력할 때 주면 틀렸다고 뜸.
			}
		}
		System.out.println(dp[k][n]);
	}

}

처음에는 println문에 1000000000을 나눠줬는데 틀렸다고 떠서 나중에 for문 안으로 옮겼다.

오버플로우 때문인듯?