[JAVA] 백준 11051 조합

 

 

 

 

11051번: 이항 계수 2

참고할 이전 문제

[JAVA] 백준 11050 조합 점화식

문제

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

풀이

11050문제와 동일한 문제이지만 10,007로 나눈 나머지를 출력하는 문제이다.

주의할 점은 마지막에 나머지 연산을 진행하면 오버플로가 발생해 오답이 된다.

나머지 연산은 언제 해주더라도 결과에 상관이 없으므로 점화식을 토대로 배열을 만들 때 나머지 연산을 진행해주었다.

📌 점화식을 통한 DP 배열 채우기

        for(int i=0; i<=N; i++){
          A[i][0] = 1;
          A[i][i] = 1;
          A[i][1] = i;
        }
        for(int i=1; i<=N; i++){
            for(int j=1; j<=K; j++){
                A[i][j] = (A[i-1][j-1] + A[i-1][j]) % 10007;
            }
        }

📌 전체 코드

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

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[][] A = new int[1001][1001];

        for(int i=0; i<=N; i++){
          A[i][0] = 1;
          A[i][i] = 1;
          A[i][1] = i;
        }
        for(int i=1; i<=N; i++){
            for(int j=1; j<=K; j++){
                A[i][j] = (A[i-1][j-1] + A[i-1][j]) % 10007;
            }
        }
        System.out.println(A[N][K]);

    }
}

결과