[BOJ_2225/JAVA] 합분해

문제

풀이

해당 문제는 다이나믹 프로그래밍으로 해결하는 문제이다.

만약, 입력이 5. 3라면 2개의 숫자을 더해서 20이 되는 경우의 수를 구하면 된다.

0(2개 더해서 0되는 경우)+ 5

1(2개 더해서 1되는 경우) + 4 

2(2개 더해서 2되는 경우) + 3

3(2개 더해서 3되는 경우) + 2

4(2개 더해서 4되는 경우) + 1 

5(2개 더해서 5되는 경우) + 0

--> dp[3][5]= dp[2][0]+dp[2][1]+...+dp[2][5] 가 될 것이다. 점화식은 dp[K-1][0]+~+dp[K-1][N]이 된다.

 

이제, 배열안에 값을 넣어보자.

dp[1][0]=1; (1개 숫자로 0을 만드는 경우)

dp[2][0]=1; (2개 숫자로 0을 만드는 경우)

dp[3][0]=1;

.

.

dp[200][0]=1;

--> dp[i][0]은 전부 1이다.

 

그리고

dp[1][1]=1; (1개의 숫자로 1을 만드는 경우)

dp[1][2]=1; (1개의 숫자로 2를 만드는 경우)

dp[1][3]=1;

.

.

dp[1][200]=1;

--> dp[1][i]도 전부 1이다.

 

그리고 위에서 도출한 점화식을 이용하면

dp[2][1]=dp[1][0]+dp[1][1] 

dp[2][2]=dp[1][0]+dp[1][1]+dp[1][2]

                  --> dp[2][1]

dp[2][3]=dp[1][0]+dp[1][1]+dp[1][2]+dp[1][2] 

                  --> dp[2][2]

.

.

따라서 점화식은 dp[K][N]=dp[K][N-1]+dp[K-1][N]이 된다.

이것을 코드로 구현해보자.

코드

package Week08;

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

public class BOJ2225 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		
		final int mod=1000000000;
		
		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=0;i<=9;i++) {
			dp[1][i]=1;
		}
		
		for(int i=1;i<=N;i++) {
			for(int j=1;j<=K;j++) {
				dp[j][i]= (dp[j][i-1]+dp[j-1][i])%mod;
			}
		}
		
		System.out.println(dp[K][N]);
	}

}

 

마지막에 출력할 때 나눠주면 틀렸다고 한다. 오버플로우때문이라고 하는데...

그래서 처음에 배열에 넣어줄때 나눠줘야한다.