[백준] 11051 이항계수2 (JAVA)

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

위의 문제는 BOJ에서 유저들이 만들어 놓은 문제집중 redbin0471님의 "단기간 성장"이라는 문제집에속해있는 문제중 하나이다.

이항계수문제의 시리즈는 1부터3까지있는데 2부터는 범위가 1000으로 늘어나서 일반적인 이항계수의

공식으로는 시간초과가 나온다.

위의 문제의 정답은 파스칼의 삼각형과 동적계획법을 이용해 풀면

쉽게 풀린다

 

파스칼의 삼각형

 

import java.io.*;

import java.util.StringTokenizer;

public class Main {
    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[N+1][N+1];

        for(int i=0; i<=N; i++) {
            for (int j = 0; j <= i; j++) {
                if (i == j || j == 0) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % 10007;
                }
            }
        }
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(String.valueOf(dp[N][K]));
        bw.flush();
        bw.close();
    }

}