문제 2225번

풀이접근

1. 이 문제는 DP관련 문제이다. 그래서 점화식을 만드려고 생각해 보았다.
2. N이 0인 경우, 0 ~ 0까지의 숫자를 사용하기 때문에 k가 몇이 되더라도 방법은 한가지 뿐일 것이다.
3. K가 1인 경우도 위와 비슷하게 N이 몇이 되더라도 1가지의 방법 밖에 없을 것이다.
4. dp[K][N] 배열에 2,3번의 내용을 저장하고 사례를 찾아보자.
   • N이 1이고 K가 2인 경우는 1+0, 0+1 2가지가 있을 것이다.
   • N이 2이고 k가 2인 경우에는 2+0, 1+1, 0+2 3가지가 있을 것이다.
     지금까지 예시만 보면 dp[k][n] = dp[k-1][n]+dp[k][n-1]로 보인다.
   • N이 1이고 K가 3인 경우에는 1+0+0, 0+1+0, 0+0+1 3가지가 있다.
   • N이 2이고 K가 3인 경우에는 2+0+0,0+2+0, 0+0+2, 1+1+0, 1+0+1, 0+1+1 6가지가 있다.
     여기까지 확인을 해보니, 위에 예상했던 점화식과 같은 결과를 가져왔다.
5. 4번에서 찾은 점화식으로 dp배열을 저장하고, 해당 k와 n에 맞는 값을 출력해 준다.

소스코드

import java.io.*;
import java.util.*;
public class boj2225 {
    public static final int MOD = 1000000000;
    public static void main(String[] args) throws IOException{
        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];
        Arrays.fill(dp[1], 1);
        for (int i = 0; i <=K; i++) {
            dp[i][0] = 1;
        }
        for (int i = 2; i <= K; i++) {
            for (int j = 1; j <= N; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
                dp[i][j] %= MOD;
            }
        }
        System.out.println(dp[K][N]);
    }
}

문제핵심

• dp, 즉 점화식 구하기