[KOITP] 합분해

출    처  : http://koitp.org/problem/SDS_PRO_2_2/read/

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
1.0 초	512 MB	1982	628 (32%)	529

문제

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

입력

첫 번째 줄에 두 정수 N, K가 공백으로 분리되어 주어진다. (1 ≤ N, K ≤ 200)

출력

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

힌트

예제 입력

20 2

예제 출력

21

< Comment >

 이번에도 점화식도 동일하게 세웠었으나, 기저케이스에 대한 명확한 정의를 하지 않고 진행하여, 결국 답안을 보고 틀린 점을 찾아내었습니다. 다른 부분은 크게 문제가 없었으나 N의 범위를 0부터로 지정하지 않나, 계산하는 과정에서 오차가 생겼던 것으로 보입니다. 이 전에 풀었던 풀이도 별해와 크게 다르지 않았는데, 조합을 이용하여 N+K-1 개 중에 K-1개를 고르는 경우의 수와 동일했습니다. 수들 사이에 칸막이를 넣어둔다는 생각은 동일했으나, 제가 처음에 풀었을때 N+1개 중에 골라야한다고 단순하게 중복없이 생각하여 문제가 풀리지 않았었습니다. 속도는 조합을 이용하는 방법이 더 빠르다고 합니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class DevideSum {
	
	public static int N = 0;
	public static int K = 0;
	
	public static double dp[][] = new double[202][202];
	
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		dp[0][0] = 1;
		for (int i = 0 ; i <= N ; i++) {
			
			for (int j = 1 ; j <= K ; j++) {
				
				for (int k = 0 ; k <= i ; k++) {
					
					dp[i][j] = (dp[i][j] + dp[i-k][j-1]) % 1000000000;
				}
			}
		}
		
		bw.write("" + String.format("%.0f",dp[N][K]));
		bw.flush();
		bw.close();
	}
}