[백준] 2225: 합분해 - JAVA

31 Aug 2023 in Algorithm on 다이나믹 프로그래밍

https://www.acmicpc.net/problem/2225

풀이

0부터 N까지의 정수 K개를 더해서 합이 N이 되는 경우의 수를 구해야 한다.

K개를 더해서 N이 되는 경우는 “K-1개를 더해서 N이 되는 경우에 0을 더한 경우”,

“K-1개를 더해서 N-1이 되는 경우에 1을 더한 경우”,

“K-1개를 더해서 N-2이 되는 경우에 2를 더한 경우”,

… “K-1개를 더해서 0이 되는 경우에 N을 더한 경우”

들의 합으로 나타낼 수 있다.

dp[k][n]에서 정수 1개를 이용해 n을 만드는 경우는 1개,

정수 k개를 이용해 0을 만드는 경우는 1개로 초기화 해주었다.

그 후 위의 경우들을 다 더하면서 저장하여 dp[k][n]을 출력하면 된다.

아래 코드에서 3중 for문에 있던

for (int l = 0; l <= j; l++) {
    dp[i][j] += dp[i - 1][j - l];
    dp[i][j] %= MOD;
}

이 코드를 다음과 같이 바꾸면 시간을 더 줄일 수 있다.

dp[i][j] += dp[i - 1][j] + dp[i][j - 1];
dp[i][j] %= MOD;

---

메모리: 14356KB

시간: 152ms

언어: Java 11

코드

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

public class Main {
    static final int MOD = 1_000_000_000;

    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());
        int k = Integer.parseInt(st.nextToken());

        int[][] dp = new int[k + 1][n + 1];
        for (int i = 0; i < n + 1; i++) {
            dp[1][i] = 1;
        }
        for (int i = 0; i < k + 1; i++) {
            dp[i][0] = 1;
        }

        for (int i = 2; i <= k; i++) {
            for (int j = 1; j <= n; j++) {
                for (int l = 0; l <= j; l++) {
                    dp[i][j] += dp[i - 1][j - l];
                    dp[i][j] %= MOD;
                }
            }
        }

        System.out.println(dp[k][n]);
    }

}