[BaekJoon] 2225 합분해 (Java)

🔗 문제 링크

https://www.acmicpc.net/problem/2225

📝 문제 설명

설명은 hu-coding님의 게시글을 참조했습니다.

해당 문제는 K개의 숫자를 더해 N을 만들 수 있는 경우의 수를 구하는 문제로 해당 문제르 해결하기 위해서는 경우의 수를 나눠야한다.

입력값이 5 3이라고 할 때 5를 만드는 방법은 다음과 같습니다.

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] 로 DP[K][N] = DP[K-1][0] + DP[K-1][1] + … + DP[K-1][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]와 같이 변할 수 있는 것을 알 수 있습니다.

해당 식을 이용하여 코드를 작성한 결과 문제를 성공적으로 통과할 수 있었습니다.

👨🏻‍💻 작성한 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		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[K+1][N+1];
		
		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;
			}
		}
		System.out.println(dp[K][N]);
 	}

}