백준/11050번/Java - 이항 계수 1

 

https://www.acmicpc.net/problem/11050

11050번: 이항 계수 1

---

5개 중 3개를 뽑는 조합의 수는 4개 중 2개를 뽑는 조합의 수와 4개중 3개를 뽑는 조합의 수의 합과 같다.

5개 중 3개를 선택할 때, 앞선 4개는 모두 선택되거나 선택되지 않았을 경우, 마지막 남은 1개 역시 선택되거나 선택되지 않는 두 가지 경우의 수 뿐이다.

마지막 남은 1개가 선택되는 경우는 앞선 4개 중 2개를 뽑은 경우이며, 선택되지 않은 경우는 앞선 4개 중 3개를 뽑은 경우이다.

따라서 i개중 j개를 뽑는 경우의 수를 arr[i][j]로 배열에서 나타낸다고 했을 때,

다음과 같은 점화식이 성립한다.

arr[i][j] = arr[i-1][j] + arr[i-1][j-1]

점화식을 통해 배열을 완성하고, 문제에서 요구하는 5C2를 구하기 위해 arr[5][2]를 출력하면 끝.

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

public class Main {

    public static void main(String[] args) throws IOException {
        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());

        // 배열의 의미 : arr[i][j] : i개중 j개를 뽑는 경우의 수
        int[][] arr = new int[N+1][N+1];
        //배열 초기화
        // arr[i][1] : i개 중 1개를 선택하는 경우의 수 이므로 i 가지
        // arr[i][0] : i개 중 1개도 선택하지 않는 경우의 수 이므로 1가지
        // arr[i][i] : 전체를 모두 선택하는 경우의 수 1가지
        for(int i=1; i<=N; i++) {
            arr[i][1] = i;
            arr[i][0] = 1;
            arr[i][i] = 1;
        }
        // 조합 점화식 : arr[i][j] = arr[i-1][j] + arr[i-1][j-1]
        // 점화식으로 배열 완성
        for(int i=2; i<=N; i++) {
            for(int j=1; j<i; j++) {
                arr[i][j] = arr[i-1][j] + arr[i-1][j-1];
            }
        }
        // n C k  구하기
        System.out.println(arr[N][K]);

        br.close();
    }

}