이항 계수 2 풀이

문제 링크: https://www.acmicpc.net/problem/11051

백준 정수론 및 조합론 8단계 - 11051번 이항 계수 2를 풀어보았다.

 

풀이: 범위가 크기 때문에 dp를 사용해 풀어야 한다. (https://cocoon1787.tistory.com/220 를 참고했다.)

파이썬의 경우 이항 계수 1보다 범위가 크기 때문에, 풀이 형식을 조금 바꾸었다.

 

C++

#include <iostream>

using namespace std;

int main()
{
	int dp[1001][1001];
	int n,k;
	cin>>n>>k;
	dp[0][0]=1;
	dp[1][0]=1;
	dp[1][1]=1;
	for(int i=2;i<=n;i++)
	{
		for(int j=0;j<=i;j++)
		{
			if(j==0) dp[i][0]=1;
			else if(j==i) dp[i][j]=1;
			else dp[i][j]=(dp[i-1][j-1]+dp[i-1][j])%10007;
		}
	}
	cout<<dp[n][k];
}

Python

n,k=map(int,input().split())
over=1 # 분모
for i in range(k):
	over*=n
	n-=1
under=1 # 분자
for i in range(2,k+1):
	under*=i
print((over//under)%10007)

Java