(백준) 2225 - 합분해 [java]

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

2225번: 합분해

🐢 설명

DP문제를 열심히 풀어야 겠다고 생각했다. 문제는 간단한데 점화식을 떠올리는게 쉽지 않았다.

N, K가 주어질 때 1 ~ N의 수가 있고 K개를 뽑아서 더해서 N을 만들어야 하는 문제이다. 이를 점화식을 나타내보자면 K개를 골라서 N을 나타내야 하므로 DP[K][N]으로 나타낼 수 있다.

 

즉, DP[K][N] : 1 ~ N의 수 중에서 K개를 뽑아서 더했을 때 N인 경우의 수 가된다.

 

이를 이용해서 점화식을 구해보면

DP[K-1][N] + 0 = DP[K][N],

DP[K-1][N - 1] + 1 = DP[K][N],

DP[K-1][N - 2] + 2 = DP[K][N],

DP[K-1][N - 3] + 3 = DP[K][N],

...

DP[K-1][N - N] + N = DP[K][N]

DP[N][K] = 합 for i range(0, K) : dp[N - 1][K - i]

로 볼 수 있다.

또한 K가 1일 때, 즉 1개만 뽑았을 때 N인 경우의 수는 전부 자기 자신인 1이므로

for i range N : DP[1][N] = 1

로 초기화 해줄수 있다.

🐢코드

//package Gold이상문제_정리;

/*
0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.
덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.
 */

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

public class Main {
    static int N, K;
    static int[][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // K개를 더해서 N을 만들어야 한다. 이때 더하는 수는 중복 가능
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        // K개를 더했을 때 N인 경우를 나타내는 DP
        // dp[K][N] = dp[K-1][N] + ... + dp[K-1][0]
        // N + 0 , (N-1) + 1, (N-2) + 2 ... (N-N) + N 는 N이므로 더했을 때 N이 되는 개수를 구할 수 있다.
        dp = new int[K+1][N+1];

        // 1개를 더했을 때 i인 경우의 수는 1개
        for (int i = 0; i <= N; i++) {
            dp[1][i] = 1;
        }

        for (int k = 1; k <= K; k++) {
            for (int n = 0; n <= N; n++) {
                for (int i = 0; i <= n; i++) {
                    dp[k][n] += dp[k - 1][n - i];
                    dp[k][n] %= 1_000_000_000;
                }
            }
        }
        System.out.println(dp[K][N]);
    }
}

🐢 마무리

dp문제를 풀어봤는데 점화식을 세우는데 어려움을 겪고있다. 좀 더 많은 문제를 오랜 고민을 가지고 풀어봐야겠다.