백준 11051번
https://www.acmicpc.net/problem/11051

문제

---

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

생각하기

---

• 이항계수를 활용
• 2차원배열을 통한 파스칼의 삼각형 구현
• DP알고리즘을 사용하고 memoization을 이용하자

동작

이항 계수 개념과 DP를 활용!

코드

---

Java

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

public class Main {
	private static final int mod = 10007;
	static int memo[][];
	
	public static void main(String[] args) throws Exception {
		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());
		memo = new int[N+1][N+1];
		DP(N);
		System.out.print(memo[N][K]);
	} // End of main
	
	private static void DP(int N) {
		for(int i=0; i<=N; i++) {
			memo[i][0] = 1;
			for(int j=1; j<=i; j++) memo[i][j] = (memo[i-1][j-1] + memo[i-1][j]) % mod;
		}
	} // End of DP
} // End of Main class

Kotlin

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

private const val mod = 10007
private lateinit var memo : Array<IntArray>
fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val st = StringTokenizer(br.readLine())
    
    var N = st.nextToken().toInt()
    var K = st.nextToken().toInt()
    memo = Array(N+1){IntArray(N+1)}
    DP(N)
    print(memo[N][K])
} // End of main

private fun DP(N : Int) {
    for(i in 0..N) {
        memo[i][0] = 1
        for (j in 1..i) memo[i][j] = (memo[i - 1][j - 1] + memo[i - 1][j]) % mod
    }
} // End of DP