[Java] 백준 2225번 합분해

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

2225번: 합분해

문제 설명

• 0~N까지 정수에서 K를 더해 합이 N이 되는 경우의 수를 구하는 것.
• 덧셈의 순서가 바뀐 경우(1+2와 2+1)는 다른 경우이다.
• 하나의 수는 중복 가능하다.  -> 즉, (1+1+0, 1+0+1, 0+1+1) 모두 다른 경우

 

처음 문제를 접했을때 점화식이 바로 생각나지 않았다. 2차 배열을 생각하여 표를 그려 생각해보면 쉽다.

N=3, K=3인 경우를 생각해보자.

0~3까지 정수 중 3개를 더해 합이 3가 되는 경우의 수를 구하는 것이다.

 

DP[N][K] 이중배열은 경우의 수를 의미한다.

표를 그려보면 다음과 같다.

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)

 

표를 그려 생각해보면 dp[N][K]= dp[N-1][K] + dp[N][K-1] 이라는 규칙을 찾을 수 있다.

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		
		int N = s.nextInt();
		int K = s.nextInt();
		
		int dp[][] = new int[N+1][K+1];
		
        //K=1일때 초기화
		for(int i=1;i<=N;i++) {
			dp[i][1]=1;
		}
		
        //N=1일때 초기화
		for(int i=1;i<=K;i++) {
			dp[1][i]=i;
		}
		
		
		for(int i=2;i<=N;i++) {
			for(int j=2;j<=K;j++) {
				dp[i][j]=(dp[i-1][j]+dp[i][j-1])%1000000000;
			}
		}

		System.out.println(dp[N][K]);
	}
}