G2225. 합분해

문제

제출 코드

• 사용 알고리즘 : DP

• K가 1인 경우부터 순차적으로, 숫자 N을 만들수 있는 경우의 수를 저장하여 계산
• 점화식 유도 과정

  k개의 수로 n을 만들어 내는 경우의 수를 dp[k][n]이라 하고 구해보면 다음과 같다.

  n을 만들기 위해 k번째로 더해지는 수를 m이라고 하자.

  

  그럴 경우 다음과 같이 1~k-1번째 수까지 더한 값에, m을 더해주면 된다

  이 경우의 수는 $dp[k-1][n-m] * dp[1][m]$

  $= dp[k-1][n-m] * 1$ $= dp[k-1][n-m]$

  으로 표현할 수 있다.

  0 ≤ m ≤ n 이므로, 모든 m에 대한 경우의 수를 더하면

  $dp[k][n] = dp[k-1][0] + … + dp[k-1][n-1] + dp[k-1][n]$ 이다.

  또한 $dp[k-1][0] + … + dp[k-1][n-1] = dp[k][n-1]$ 이므로, $dp[k][n] = dp[k][n-1] + dp[k-1][n]$ 이라 할 수 있다.

package gold;

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

public class G2225_decompose {

	public static void main(String[] args) throws IOException {
		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());

		long[][] dp = new long[K+1][N+1];

		for(int k=1; k<=K; k++) {
			for(int n=0; n<=N; n++) {
				if(k==1 || n==0) dp[k][n] = 1;
				else dp[k][n] = (dp[k][n-1] + dp[k-1][n])%1000000000;
			}
		}

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

}