[JAVA]합분해(Baekjoon)

문제

문제

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

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

입력

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

출력

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

 

예제 입력 1

20 2

예제 출력 1

21

예제 입력 2

6 4

예제 출력 2

84

풀이

처음 문제를 잘못 이해해서 고생을 했다. 하지만, 문제를 완벽히 이해하는 게 우선이기에 계속 다시 읽어 이해했다.

DP 문제를 찾아 풀었기 때문에 DP를 사용해야 한다는 것을 알고 시작한다.

직관적으로, DP로 풀려고 접근했을때 $dp[k][i]$ 를 0부터 i까지의 정수 k개를 더해 합이 i가 되는 경우의 수라고 하고 점화식을 세운다.

$dp[0][0]$은 1개의 경우가 있다. 아무 정수도 안 더하는 경우이다. 0개의 정수를 사용해 0을 만들었으니 $dp[0][0] = 1$이라고 할 수 있다.

$dp[1]$의 경우를 보면, 각각 i에 해당하는 정수 1개를 이용해 가능하다. $dp[1][i] = 1 (i를 사용)$

$dp[2]$의 경우를 보자. $dp[2][0]$은 1이다. 0+0의 경우. $dp[2][1]$은 2이다. 1+0과 0+1의 경우. 이는 다음과 같이 해석할 수 있다. $dp[1][1]$(1개의 정수를 사용해 1을 만드는 경우의 수)에다가 정수 0을 더하는 경우의 수 + $dp[1][0]$(1개의 정수를 사용해 0을 만드는 경우의 수)에다가 정수 1을 더하는 경우의 수. 즉, $dp[k][i]$는 $\sum{dp[k-1][i]} , \forall i\in[0,k-1]$이다.

그러나, 다른 사람의 풀이를 보고 더 효율적인 접근을 배웠다. 시간복잡도는 동일하나, 메모리를 상당히 적게 쓰는 방법이다.

1. $dp[k]$를 구할 때는 $dp[k-1]$만 조회를 한다. 따라서, k-2까지의 배열들을 필요가 없다.
2. i가 0부터가 아닌 k-1부터 반복문을 수행한다면, dp[k-2]는 전 스테이지의 내용이기에 1차원 배열만으로 수행할 수 있다.

코드

import java.util.*;
import java.io.*;

public class _2225 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()), K = Integer.parseInt(st.nextToken());
        long[] dp = new long[N+1];
        for(int i = 0; i <= N; i++)
            dp[i] = 1;
        for(int i = 1; i < K; i++){
            // System.out.println(String.format("stage%d:\t",i)+Arrays.toString(dp));
            for(int j = N; j >= 0; j--){
                for(int l = 1; l <= j; l++){
                    dp[j] += dp[j-l];
                    dp[j] %= 1_000_000_000;
                }
            }
        }
        System.out.println(dp[N]);
    }
}