[백준] 11051번 - 이항 계수 2 [Java]

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

 

[백준] 11051번 - 이항 계수 2 [Java]

---

1.  아이디어

 

이전 이항 계수 문제에서 수의 범위가 커진 문제로 단순한 재귀 대신 다이나믹 프로그래밍을 활용해서 해결할 수 있다.

---

2. 문제풀이

 

Top-Down, Bottom-Up 두 가지 방식으로 구현했는데 Top-Down 방식은 기존의 재귀 함수에서 행을 N, 열을 K로 하는 2차원 dp 테이블을 설정해서 dp 테이블에 값이 있으면 바로 반환하고 기존의 반환값도 dp 테이블에 저장하는 방식으로 구현했다. Bottom-Up 방식은 똑같은 dp 테이블에서 조합 점화식을 적용해 반복문으로 구하는 방식으로 구현했다.

---

3. 코드

 

import java.io.*;
import java.util.*;

public class Main_TopDown_DP {

    private static final int MOD = 10007;
    private 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());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

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

        int ans = recur(N, K);
        System.out.println(ans);
    }

    private static int recur(int N, int K) {
        if (dp[N][K] != 0) return dp[N][K];
        if (K == 1) return N;
        if (K == 0 || N == K) return 1;
        return dp[N][K] = (recur(N - 1, K - 1) + recur(N - 1, K)) % MOD;
    }

}

import java.io.*;
import java.util.*;

public class Main_BottomUp_DP {

    private static final int MOD = 10007;

    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[1 + N][1 + K];
        for (int i = 0; i <= N; i++) {
            dp[i][0] = 1;
        }

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

        System.out.println(dp[N][K]);
    }
}

---

4. 후기

 

- Top-Down

- Bottom-Up