23. 2225번 합분해

 

문제만보면 알아보기 힘들었던 문제

다이나믹 프로그래밍 문제가 다 그렇듯이 초반 작은 문제 몇번을 손으로 반복하면 규칙이보인다.

 

N(만들어야하는 수) K(사용가능한 갯수)

N=1 일때

K=1 이면 1 - 1개

K=2 이면 (1+0),(0+1) -2개

K=3 이면 (1+0+0),(0+1+0),(0+0+1) -3개

 

N=2 일때

K=1 이면 2 - 1개

K=2 이면 (2+0),(1+1),(0+2) - 3개

K=3 이면 (1+1+0),(1+0+1),(0+1+1),(2+0+0),(0+2+0),(0+0+2) - 6개

 

N=3 일때

K=1 이면 3 - 1개

K=2 이면 (0+3),(1+2),(2+1),(3+0) - 4개

K=3 이면 (0+0+3),(0+1+2),(0+2+1),(0+3+0),(1+0+2),(1+1+1),(1+2+0),(2+0+1),(2+1+0),(3+0+0) - 10개

 

 

표로 그려본다면

K / N	0	1	2	3
0	0	1	1	1
1	1	1	2	3
2	1	1	3	6
3	1	1	4	10

 

이렇다 이때 이해하기 쉬울려면 파란색으로 적힌 6을보면된다 

K,N(2,3)6은 바로위 K,N(1,3) + K,N(2,2) 의 값과 같고

K,N(3,3)10은 바로위 K,N(2+3) + K,N(3,2) 의 값과 같다.

 

이를 식으로 나타내면

KN(A,B) = KN(A-1,B) + KN(A,B-1) 로 표현할수 있다

 

이걸 코드화 해보자

import java.util.Scanner;
public class training {

	public static void main(String[] args) {
		Scanner SC = new Scanner(System.in);
		int N = SC.nextInt(); // n 입력받음
		int K = SC.nextInt(); // k 입력받음
		
		int[][] DP = new int[201][201]; // 200까지 가능하니 +1 시켜 배열을 만든다
		
		for(int i=1;i<=K;i++) {
			DP[i][0]=1;
		}
		for (int i=1; i<= K; i++) {
			DP[1][i]=i;
		}
		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]);
	}

}

 

결과