[BOJ] 백준 11051 이항 계수 2

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

 Input 
5 2

 Output 

10　

 

[BOJ] 11050 이항 계수 1 문제처럼 재귀방식으로 접근하면 시간제한이 걸립니다.

[BOJ] 백준 11050 이항 계수 1

불필요하게 재귀호출되는 bino(n, k)를 DP 방식으로 처리

 

 

[Bottom-up 방식]

import java.util.Scanner;
 
public class Main{
    static final int DIVIDER = 10007;
    static int[][] cache;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.next());
        int K = Integer.parseInt(sc.next());
         
        // 인덱스를 '1'부터 하기 위함
        cache = new int[N+1][K+1];
        for(int i=1; i<=N; i++) {
            for(int j=0; j<=K; j++) {
                if(i == j || j == 0) {
                    cache[i][j] = 1;
                }else {
                    cache[i][j] = cache[i-1][j] + cache[i-1][j-1];
                    cache[i][j] %= DIVIDER;
                }
            }
        }
         
        System.out.println(cache[N][K]);
    }    
}

---

import java.util.Scanner;
 
public class Main{
    static final int DIVIDER = 10007;
    static int[][] cache;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.next());
        int K = Integer.parseInt(sc.next());
         
        // 인덱스를 '1'부터 하기 위함
        cache = new int[N+1][K+1];
         
        System.out.println(bino(N,K));
    }
 
    private static int bino(int n, int k) {
        if(n == k || k == 0) {
            return 1;
        }
         
        // 메모이제이션 기법 사용
        if(cache[n][k] != 0) {
            // 값이 저장되어 있다면 재귀호출을 하지않고 저장된 값을 반환
            return cache[n][k];
        }
         
        // 저장되어 있지 않으면 재귀호출을 하지만 중복계산은 없다.
        cache[n][k] = bino(n-1,k) + bino(n-1,k-1);
         
        return cache[n][k] % DIVIDER;
    }
}