[백준, 자바] 2225번 - 합분해

문제 링크
https://www.acmicpc.net/problem/16194

최종 코드(정답)

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int K = Integer.parseInt(input[1]);

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

        for(int i = 1; i <=N; i++) {
            dp[i][1] = 1;
        }

        for(int j = 1; j <=K; j++) {
            dp[1][j] = j;
        }

        /**
         * 위의 두 for문 대신에 애초에 201로 해서 for문으로 단번에 초기화할 수도 있다.
         * int[][] dp = new int[201][201];
         * for (int i = 1; i <= 201; i++) {
         *    dp[i][1] = 1;
         *    dp[1][i] = i;
         * }
         */

        for(int h = 2; h<=N; h++) {
            for(int l = 2; l<=K; l++) {
                dp[h][l] = (dp[h-1][l] + dp[h][l-1]) % 1000000000;
            }
        }
        System.out.println(dp[N][K]);
    }
}

풀이
골드는 어렵다;; 2가지 방법이 있는데,

• 재귀 함수를 사용해서 푼다.

public class Main {
    public static final int MOD = 1_000_000_000;
    static long[][] memo;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new java.io.InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        memo = new long[N+1][K+1];
        System.out.println(dp(N, K));
    }

    public static long dp(int N, int K) {
        if(memo[N][K] == 0) {
            if (K == 1) {
                return 1;
            }
            long count = 0;
            for (int i = 0; i<=N; i++) {
                count += dp(N-i, K-1);
            }
            memo[N][K] = count % MOD;
        }
        return memo[N][K];
    }
}

• 초기화를 한 다음에 이중 for문으로 처리한다.

이 코드를 보고 K가 1일 때 return 1하는 코드를 이해하지 못했었음.

if (K == 1) 조건은 기본 케이스를 처리합니다.
K가 1이라는 것은 숫자 N을 한 번만 사용할 수 있다는 것을 의미합니다. 이 경우, 방법의 수는 1가지입니다. 따라서 return 1;이 실행됩니다.
이 값은 memo[N][K]에 저장되지 않지만, 이는 문제가 없습니다.
왜냐하면 dp(N, K) 함수는 memo[N][K]가 0인 경우에만 호출되기 때문입니다. 즉, memo[N][K]에 값이 이미 저장되어 있다면, dp(N, K) 함수는 호출되지 않습니다.
따라서, K == 1일 때 return 1;이 실행되면, 이 값은 memo[N][1]에 저장되지 않지만, 이후에 dp(N, 1)이 호출되면 항상 1을 반환하므로 문제가 없습니다.
또한, dp(N-i, K-1)에서 K-1이 되는 경우, 이는 K가 2 이상일 때만 발생합니다. 따라서 K-1이 1이 되는 경우에는 항상 dp(N-i, 1)이 호출되고, 이는 항상 1을 반환하므로 문제가 없습니다.

나의 경우 이중 for문이랑

정수 1개로 N을 만드는 경우는 N개다.
정수 2개를 가지고 N을 만드는 경우는 N+1개다.

한 정수를 미리 지정한 뒤에, 정수 2개의 경우로 계산한다. N을 만들수 있는 모든 경우를 다 합해줘야 한다.

예를 들어 N이 5고 K가 3이라면 기본 초기화 한 dp는 아래와 같다.

1 2 3 
1
1
1
1

이렇게 깔고 일단 시작한다.
그리고 dp[1][1]부터는 본인의 왼쪽,아래쪽 값을 더해서 본인에게 저장한다.

dp[1][1] = 3(1+2)
dp[1][2] = 6(3+3)
dp[2][1] = 4(1+3)
dp[2][2] = 10(4+6)
dp[3][1] = 6(1+5)
dp[3][2] = 21(6+15)

최종적으로 dp[N][K]의 값을 가져온다.

N을 K개로 몇가지로 표현할 수 있을까?
K가 증가함에 따라 N을 표현하는 개수는 어떠한 형태로 누적될까?
N와 K, 2개 기준으로 N*K의 2차원 배열을 생성한다.

뭐 이런 질문들 던져가면서 궁리를 했다.