[99클럽 5기 코테 스터디 TIL 24일차] 합분해 (feat. 동적계획법)

1) 문제

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

 

2) 풀이

코드 설명

1. 입력 받기: N과 K를 입력으로 받습니다.
2. DP 배열 초기화: dp[i][j]는 i개의 수로 합이 j가 되는 경우의 수를 저장하는 배열입니다. 이 배열을 K + 1과 N + 1 크기로 생성합니다.
3. 초기 조건: dp[0][0] = 1로 설정합니다. 이는 0개를 사용해서 합이 0이 되는 방법은 1가지라는 의미입니다.
4. DP 테이블 채우기:
   • i가 1부터 K까지 반복됩니다. 즉, i개를 사용해서 합을 만들 때를 고려합니다.
   • j가 0부터 N까지 반복됩니다. 즉, 합이 j일 때를 고려합니다.
   • k는 0부터 j까지 반복되며, dp[i][j]는 dp[i-1][j-k]를 더하는 방식으로 점차 채워집니다. 이 과정에서 k는 한 번에 더할 수 있는 수를 의미합니다.
   • 합이 j가 되는 경우의 수를 계산하기 위해 이전 단계에서 가능한 모든 k값에 대해 더합니다.
5. 결과 출력: 최종적으로 dp[K][N]이 우리가 구하려는 값입니다. 이를 출력합니다.

• 이 코드의 시간 복잡도는 O(K * N * N)입니다. 즉, K번 반복하며 각 반복마다 N번, 그리고 각 j마다 또 N번 반복됩니다.
• 하지만 주어진 K와 N이 최대 200이므로, 200 * 200 * 200의 계산은 가능한 범위입니다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        
        // DP 배열 초기화
        long[][] dp = new long[K + 1][N + 1];
        final int MOD = 1000000000;

        // dp[0][0] = 1, 0개로 0을 만드는 방법은 1가지 (빈 합)
        dp[0][0] = 1;

        // DP 배열 채우기
        for (int i = 1; i <= K; i++) { // i개 수로 만들 때
            for (int j = 0; j <= N; j++) { // 합이 j일 때
                for (int k = 0; k <= j; k++) { // k값을 더해주면서
                    dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % MOD;
                }
            }
        }

        // 결과 출력
        System.out.println(dp[K][N]);
    }
}