백준 11050, 11051 - 이항 계수 1,2

Java

11050, 11051 번 - 이항 계수 1,2

문제

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

접근 방법

2차원 배열과 DP를 통해 해결하였다.
이항 계수 _NC_K는 _N-1C_K + _N-1C_K-1와 같다.
따라서 위 식이 점화식이 되며, N과 K가 같거나 0이면 값은 1이다.
또한 N보다 K가 큰 이항 계수는 존재하지 않으므로 넘긴다.

코드

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

public class Main {
	static int n, result, k;
	static int[][] NK;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	k = stoi(stk.nextToken());
    	
    	NK = new int[n + 1][k + 1];
    	
    	for(int i = 0; i <= n; i++) {
    		for(int j = 0; j <= k; j++) {
    			if(i < j)		// 2C5 와 같은 이항 계수는 존재하지 않으므로 pass
    				continue;
    			if(i == 0 || j == 0 || i == j)	// 0C2 or 2C0 or 2C2 모두 값은 1이다.
    				NK[i][j] = 1;
    			else {
    				NK[i][j] = (NK[i-1][j] + NK[i-1][j-1]) % 10007;
    			}
    		}
    	}
    	
    	System.out.println(NK[n][k]);
    	
    	br.close();
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

점화식의 기초 문제

개선할 점

없습니다.