반응형
문제
자연수 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를 푸는 그림을 한 번 더 첨부하겠다.
코드
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 |