[백준 11051] 이항계수 2 (Java) - 조합

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

이항 계수 2 

문제

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

입력

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

출력

 (NK)\(\binom{N}{K}\)를 10,007로 나눈 나머지를 출력한다.

예제 입력 1 복사

5 2

예제 출력 1 복사

10

 

---

풀이

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 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());
        int[][] D = new int[N+1][N+1];

        // 이항계수 배열 초기화
        for(int i=1; i<N+1; i++){
            D[i][1] = i; // i개 중 1개 뽑는 경우의 수 : i개
            D[i][0] = 1; // i개 중 아무것도 뽑지 않는 경우의 수 : 1개
            D[i][i] = 1; // i개 중 i개 뽑는 경우의 수 : 1개
        }

        for(int i=2; i<N+1; i++){
            for (int j=1; j<i; j++){
                D[i][j] = D[i-1][j] + D[i-1][j-1];
                D[i][j] = D[i][j] % 10007;
            }
        }

        System.out.println(D[N][K]);
    }
}

• 조합의 점화식을 활용해서 풀이하는 문제
• 예를들어 5개의 데이터에서 3개를 선택하는 조합의 경우의 수를 생각해보자

1

2

3

4

5

• 5개의 데이터 중  4개를 이미 선택이 완료된 데이터라고 가정해보자
• 그렇다면 마지막 데이터를 선택할건지, 선택하지 않을건지에 따라 경우의 수가 달라질 것이다.
  • 선택하는 경우 : 4개의 데이터 중 2개의 데이터가 선택됨
  • 선택하지 않는 경우 : 4개의 데이터 중 3개의 데이터가 선택됨
• 이것을 일반화해서 점화식으로 나타내보면
  • 5C3 = 4C2 + 4C3이다.
• n개의 데이터 중 k개를 선택한다고 하면
  • nCk = (n-1)C(k-1) + (n-1)Ck 이다.
  • 이를 활용해서 미리 D[N+1][N+1]배열에 모두 계산해서 저장한다.

        // 이항계수 배열 초기화
        for(int i=1; i<N+1; i++){
            D[i][1] = i; // i개 중 1개 뽑는 경우의 수 : i개
            D[i][0] = 1; // i개 중 아무것도 뽑지 않는 경우의 수 : 1개
            D[i][i] = 1; // i개 중 i개 뽑는 경우의 수 : 1개
        }

• D배열을 초기화 해줄건데, 미리 값을 넣을 수 있는 값은 넣는다. 
  • for문을 1 ~ N까지 순회하면서
  • i개 중 1개를 뽑는 경우의 수 : i개
  • i개 중 아무것도 뽑지 않는 경우의 수 : 1개
  • i개 중 i개를 뽑는 경우의 수 : 1개

        for(int i=2; i<N+1; i++){
            for (int j=1; j<i; j++){
                D[i][j] = D[i-1][j] + D[i-1][j-1];
                D[i][j] = D[i][j] % 10007;
            }
        }

• 위 일반화 점화식을 활용하여 값을 채워준다.
• 10007로 나눈 나머지로 아예 연산해서 저장한다.
• 그리고 원하는 값D[N][K]를 출력하면 된다.