[JAVA]이항 계수 1(Baekjoon)

문제

문제

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

입력

 첫째 줄에 $N$과 $K$가 주어진다.$\quad(1 ≤ N ≤ 10,\quad0 ≤ K ≤ N)$

출력

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

 

예제 입력 1

5 2

예제 출력 1

10

풀이

 조합론에서, 이항 계수(binomial coefficient)는 이항식을 이항 정리로 전개했을 때 각 항의 계수이며, 주어진 크기의 조합의 가짓수이다.

$$
\binom{N}{K}=
\begin{cases}
n!/(k!(n-k)!) &0 \le k \le n \
0 &k < 0 \
0 &k > n
\end{cases}
$$

 위 식을 그대로 작성하여 이 문제를 해결하였다.

public class _11050 {
    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());
        System.out.println(binomial_coeffiecient(N, K));
    }

    public static int binomial_coeffiecient(int N, int K){
        if(K < 0 || K > N)
            return 0;
        int res = 1;
        for(int i = K+1; i < N+1; i++)
            res *= i;
        for(int i = 1; i < N - K + 1; i++)
            res /= i;
        return res;
    }
}

결론

 조합의 경우도 자주 사용되는 내용인 만큼 위 식을 기억하고 있어야겠다.