BOJ 백준온라인져지 11051 이항 계수 2 풀이

저번에 푼걸로는 못 푼다고한다.

그래서 위키백과에서 설명하는 점화식을 사용해서 풀었다.

nCr = n-1Cr-1 + n-1Cr

1. memoization

	import java.util.*;
	import java.io.*;
	/**
	* https://www.acmicpc.net/contest/problem/11051
	* BOJ 백준온라인져지 11051 이항 계수 2 풀이
	*/
	public class Main {
	private static int[][] arr;
	public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	String str1[] = br.readLine().split(" ");
	int N = Integer.parseInt(str1[0]);
	int K = Integer.parseInt(str1[1]);
	arr = new int[N + 1][K + 1];
	bw.write(String.valueOf(r(N, K)));
	bw.flush();
	}
	private static int r (int n, int k) {
	if (n == k || k == 0) return 1;
	if (arr[n][k] > 0) return arr[n][k];
	return arr[n][k] = (r(n - 1, k - 1) + r(n - 1, k)) % 10007;
	}
	}

view raw Main.java hosted with ❤ by GitHub

문제

자연수 $N$과 정수 $K$가 주어졌을 때 이항 계수 $(\genfrac{}{}{0ex}{}{N}{K})$를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 $N$과 $K$가 주어진다. (1 ≤ $N$ ≤ 1,000, 0 ≤ $K$ ≤ $N$)

출력

 $(\genfrac{}{}{0ex}{}{N}{K})$를 10,007로 나눈 나머지를 출력한다.