🧩 Baekjoon 11050 - 이항 계수 1

문제

자연수 N과 정수 K가 주어졌을 때 이항 계수 binom{N}{K}를 구하는 프로그램을 작성하시오.

입력

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

출력

binom{N}{K}를 출력한다.

예제

✅ 입력 1

5 2

✅ 출력 1

10

작성 코드

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.StringTokenizer;  
  
public class Main {  
    private static final long[][] dp = new long[11][11];  
  
    public static void main(String[] args) throws IOException {  
        // 1. 변수 선언 및 초기화  
        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());  
        
        // 2. 처리 및 출력  
        System.out.println(nCr(n, k));  
    }  
    
    private static long nCr(int n, int r) {  
        if (r == 0 || n == r) return 1;  
        if (dp[n][r] != 0) return dp[n][r];  
        
        return dp[n][r] = nCr(n-1, r-1) + nCr(n-1, r);  
    }  
}

• 페르마의 소정리를 이용하여 모듈러 연산을 사용하는 방법도 있지만 심화 문제가 존재하는 것 같아 이번에는 재귀를 이용하여 간단하게 구현해보았다.