[백준] - 11050번

[Bronze I] 이항 계수 1 - 11050번

• 문제 설명

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

입력
첫째 줄에 N과 K가 주어진다.

조건
(1 ≤ N ≤ 10, 0 ≤ K ≤ N)

출력
$\begin{pmatrix}N\\K\\ \end{pmatrix}$를 출력한다.

이항계수

• 조합론에서 이항 계수는 크기가 N인 유한 집합의 크기가 K인 부분집합의 수이다. 즉, N개의 중에서 K개를 선택했을 때 경우의 수다.

여러 성질 중 항등식에 관한 것 2개

• $\begin{pmatrix}N\\K\\ \end{pmatrix}$ = $\begin{pmatrix}N\\N-K\\ \end{pmatrix}$
  • N = 5, K = 2 일 경우 5개에서 2개를 고르는 경우의 수와 3개를 고르는 경우의 수는 같다.
• $\begin{pmatrix}N\\K\\ \end{pmatrix}$ = $\begin{pmatrix}N - 1\\K - 1\\ \end{pmatrix}$ + $\begin{pmatrix}N - 1\\K\\ \end{pmatrix}$
  • 점화식 관련이지만 쉽게 생각해서 N을 세로 K를 가로로 두었을 때 파스칼의 삼각형을 보았을때 각 사선 위를 합한 값과 동일한 것을 볼 수 있다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(bufferedReader.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[] temp = new int[K + 1];
        temp[0] = 1;

        for (int i = 1; i <= N; i++) {
            for (int j = Math.min(i, K); j > 0; j--) {
                temp[j] = temp[j] + temp[j - 1];
            }
        }
        System.out.print(temp[K]);
    }
}

1. 첫 번째 반복문은 파스칼의 삼각형의 각 행을 나타낸다.
   i가 1부터 N까지 증가하면서 각 행을 생성한다.
   단, temp[0]은 1로 파스칼 삼각형의 꼭지점이다.

2. 두 번째 반복문은 각 행의 요소다. j가 Math.min(i, K)부터 1까지 감소하면서 각 행의 요소를 생성한다.
   여기서 Math.min(i, K)는 현재 행의 요소 수를 제한한다.

3. 왼쪽 위 요소 temp[j]와 오른쪽 위 요소 temp[j - 1]의 합으로 계산하여 temp[j]값을 치환. 이것은 파스칼의 삼각형에서 각 요소가 왼쪽 위 요소와 오른쪽 위 요소의 합과 같다는 것을 이용한다.

이 코드는 파스칼의 삼각형을 사용하여 이항 계수를 계산한다.
이차배열로 값을 저장해 놓는 방식이 아니기에 값을 재활용하거나 다른 계산이 필요하면 처음부터 다시 계산해야한다.