[BaekJoon] 2225번 합분해 (Java) 문제 풀이 [Gold 5]

문제

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

2225번: 합분해

 

어떻게 풀 것인가?

문제는 상당히 짧다. 하지만 고민은 많이해야하는 문제였다.

우선적으로 문제에 대해서 고민을 하면 다이나믹 프로그래밍이라는 것을 알 수 있다.

하지만 다이나믹 프로그래밍에서 중요한 점화식에 대해서 고민이 상당히 오래걸렸다.

(내가 오랜만에 풀어서 그런걸 수도 있다....)

 

나는 문제를 2시간 가량 고민하다가 결국엔 다른 분의 풀이를 참조했다.

아래를 잘 보자.

 

1. N=1일때

K=1인경우 : 1가지 (1)
K=2인경우 : 2가지 (1+0, 0+1)
K=3인경우 : 3가지 (0+1+1, 1+0+1, 1+1+0)

 

2. N=2일때

K=1인경우 : 1가지 (2)
K=2인경우 : 3가지 (2+0, 0+2, 1+1)
K=3인경우 : 6가지 (2+0+0, 0+2+0, 0+0+2, 0+1+1, 1+0+1, 1+1+0)

 

3. N=3일때

K=1인경우 : 1가지 (3)
K=2인경우 : 4가지 (2+1, 1+2, 3+0, 0+3)
K=3인경우 : 10가지 (3+0+0, 0+3+0, 0+0+3, 1+1+1, 2+0+1, 1+0+2, 0+1+2, 0+2+1, 1+2+0, 2+1+0)

 

위와 같은 과정으로

dp[N][K] = dp[N-1][K] + dp[N][K-1] 이라는 점화식을 구할 수 있다.

 

풀면서 놓쳤던점

다이나믹 프로그래밍은 처음에 풀 때 점화식을 떠올리기가 어렵다.

그래서 그 부분을 많이 놓쳤다.

 

이 문제를 통해 얻어갈 것

수학을 곁들인 다이나믹 프로그래밍

 

내 코드 

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

public class Main {

    static int N;
    static int K;

    static int MOD = 1_000_000_000;

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

        int result = countWaysToSum();
        System.out.println(result);
    }

    public static int countWaysToSum() {
        int[][] dp = new int[N + 1][K + 1];
        for (int i = 0; i <= N; i++) {
            dp[i][0] = 0;
            dp[i][1] = 1;
        }

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

        for (int i = 2; i <= N; i++) {
            for (int j = 2; j <= K; j++) {
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % MOD;
            }
        }

        return dp[N][K];
    }
}

 

참고

https://velog.io/@kyu9610/JAVA-%EB%B0%B1%EC%A4%80-2225%EB%B2%88-%ED%95%A9%EB%B6%84%ED%95%B4

[JAVA] 백준 2225번 : 합분해