반응형

문제

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

입력

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

출력

(NK)를 10,007로 나눈 나머지를 출력한다.

예제 입력 1

5 2

예제 출력 1

10

나의 풀이

원래 이항 계수 1 문제가 조합을 푸는 식을 가지고 푸는 문제이고 이 문제가 2차원 배열을 사용해 dp로 푸는 문제였던것 같다. 나는 이미 1번 문제에서 dp로 풀어서 코드를 복붙하고 10,007로 나누어주니 문제를 풀 수 있었다. 아래 dp를 푸는 그림을 한 번 더 첨부하겠다.

IMG_F13A9FEEEF28-1

코드

import java.util.Scanner;

/**
 * 11051번 이항 계수 2
 */
public class Baeckjun11051 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();

        int[][] dp = new int[n+1][n+1];

        for (int i=0; i<=n; i++) {
            for (int j=0; j<=i; j++) {
                if (j==0 || i==j) dp[i][j] = 1;
                else dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % 10007;
            }
        }

        System.out.println(dp[n][k]);
    }
}
반응형

'Programming > Algorithm' 카테고리의 다른 글

[백준1676번] 팩토리얼 0의 개수  (0) 2020.01.19
[백준9375번] 패션왕 신해빈  (0) 2020.01.19
[백준11050번] 이항 계수 1  (0) 2020.01.19
[백준3036번] 링  (0) 2020.01.19
[백준2981번] 검문  (0) 2020.01.18

BELATED ARTICLES

more