문제
자연수 N과 정수 K가 주어졌을 때, 이항 계수 C(N, K)를 10,007로 나눈 나머지를 구하는 문제이다. C(N, K)는 N개 중 K개를 순서 없이 선택하는 경우의 수를 나타낸다.
입력
- 첫 번째 줄: 정수 N (1 이상 1,000 이하)과 K (0 이상 N 이하)
출력
C(N, K)를 10,007로 나눈 나머지를 출력한다.
예제
| 입력 | 출력 |
|---|---|
5 2 | 10 |
풀이
파스칼의 삼각형 점화식 C(n, k) = C(n-1, k-1) + C(n-1, k)를 메모이제이션 DP로 구현하여 C(N, K)를 계산한다.
dp[n][k]를 C(n, k) mod 10007로 정의한다.- 기저 조건:
k == 0또는n == k이면dp[n][k] = 1을 반환한다. dp[n][k] > 0이면 이미 계산된 값이므로 바로 반환한다.- 그 외에는
(recur(n-1, k-1) + recur(n-1, k)) % 10007로 재귀 계산하여 저장한다.
핵심 아이디어: 파스칼의 삼각형 점화식은 C(n, k)를 C(n-1, k-1)과 C(n-1, k)의 합으로 분해한다. 메모이제이션을 적용하면 중복 계산 없이 O(NK) 시간에 해결 가능하다. 각 단계에서 10007로 나머지를 취하여 오버플로우를 방지한다.
코드
package com.ssafy.an.day099;
import java.util.Scanner;
public class Day57BOJ11051이항계수2 { // 이항 계수 2
static final int DIV = 10007;
static int N, K;
static int[][] dp;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); // 자연수 N
int K = sc.nextInt(); // 정수 K
dp = new int[N + 1][K + 1];
System.out.println(recur(N, K));
sc.close();
}
private static int recur(int n, int k) {
if (dp[n][k] > 0) return dp[n][k];
if (k == 0 || n == k) return dp[n][k] = 1;
return dp[n][k] = (recur(n - 1, k - 1) + recur(n - 1, k)) % DIV;
}
private static int factorial(int n) {
return (n < 2) ? n : factorial(n - 1) * n;
} // 안씀
private static int modInverse(int a, int p) {
int ret = 1;
while (p > 0) {
if (p % 2 == 1) {
ret *= a;
p--;
ret %= DIV;
}
a *= a;
a %= DIV;
p >>= 1;
}
return ret;
} // 안씀
}복잡도
- 시간: O(N x K) — dp 테이블의 각 셀을 최대 한 번 계산
- 공간: O(N x K) — dp 배열 (N+1) x (K+1)