[Baekjoon] 11051 - 이항 계수 2

📝 문제

 

 

🔑 풀이 과정

이 문제의 핵심 2가지는 DP 배열(조합론), 모듈러 연산의 분배법칙이다.

① N이 최대 1000까지 이므로, 일반적인 팩토리얼 계산법으로 하면 범위가 초과한다.

(*참고: 12!이 int 범위를 넘기고, 20!이 long 범위를 넘긴다.)

그러므로 조합 점화식을 사용한 DP 배열을 사용해 풀이한다.

 

② 또한 이항계수(N, K)를 10007로 나눈 나머지를 구하는게 목표이므로, 모듈러 연산의 분배법칙을 사용해준다.

- 공식

nCk % 10007
D[n][k] % 10007
(D[n-1][k-1] + D[n-1][k]) % 10007
((D[n-1][k-1] % 10007) + (D[n-1][k] % 10007)) % 10007

 

 

 

🔓 답안

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[][] D = new int[N+1][N+1];

        for(int i = 0; i <= N; i++){
            D[i][i] = 1;
            D[i][1] = i;
            D[i][0] = 1;
        }

        //i가 3부터 시작하는 이유: 2행(i=2)까지는 바로 위 for문을 통해 값이 다 채워진다.
        //j가 2부터 i 전까지 수행되는 이유: 위 for문을 통해 0, 1, i일때의 값이 다 채워졌기 때문
        for(int i = 3; i <= N; i++){
            for(int j = 2; j < i; j++){
                D[i][j] = ((D[i-1][j-1] % 10007) + (D[i-1][j] % 10007)) % 10007;
            }
        }

        bw.write(D[N][M] + "\n");
        bw.flush();
        bw.close();
    }

}

 

 

 

🖤 알고리즘 분류

- 수학

- 다이나믹 프로그래밍

- 조합론