문제접근
•
이항계수
놓쳤던 부분
•
% 10007을 어디서 할거냐가 중요한데, 의 공식을 이용하게 되면
다음과 같은 문제가 생길 수 있다.
n! % 10007과 (n-k)! % 10007의 경우에서 전자의 경우에서 10007을 넘고 후자의 경우에서 10007을 넘지 않는 경우 이상한 값을 초래한다
코드
5932 KB
4 ms
#include <iostream>
int n, k;
int dp[1001][1001];
void input_setting()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
}
void input()
{
std::cin >> n >> k;
}
void solution()
{
for (int i = 0; i <= n; i++)
for (int j = 0; j <= k; j++)
{
if (i == j || j == 0)
dp[i][j] = 1;
else
dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % 10007;
}
}
void print()
{
std::cout << dp[n][k];
}
int main(void)
{
input_setting();
input();
solution();
print();
return (0);
}
C++
복사
