백준 2225 합분해 (JAVA 자바)

문제 출처 - https://www.acmicpc.net/problem/2225

2225번: 합분해

 

문제

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

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

 

 

입력

첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.

 

 

출력

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

 

문제 유형

DP

 

코드 

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

public class BJ2225_합분해 {
	static int dp[][];
	static int N, K, res;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		dp = new int [201][201];
		
		for (int i = 0; i < 201; i++) {
			dp[1][i] = i;
			dp[i][1] = 1;
		}
		
		for (int i = 2; i < 201; i++ ) {
			for (int j = 2; j < 201; j++) {
				dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 1000000000;
			}
		}
		
		System.out.println(dp[N][K]);
	}
}

처음에는 조금 당황했지만 조금 익숙한 유형이라고 해야하나 푸는 법이 조금은 뻔한 문제라서 금방 해결할 수 있었다. 주어지는 n이 작아서 그냥 다 채워버리는 걸로 했다. 만약에 해결해야 하는 문제 수가 여러개였다면 이렇게 푸는 방식이 더 경제적이었을 것이다.