[백준] 11051번 이항 계수 2 (python,c++)

https://www.acmicpc.net/problem/11051

11051번: 이항 계수 2

 

숫자가 너무 크기때문에 10,007로 나눈 나머지를 구하라는 것이다.

---

SOLUTION CODE

# PYTHON

 

순수 풀이(시간 초과)

import sys

MOD = 10007
sys.setrecursionlimit(10**7)

N,K = map(int,input().split())

def bino(n,k):
    if k==0 or k== n:
        return 1
    return bino(n-1,k-1) + bino(n-1,k)
    
print(bino(N,K))

 

재귀

import sys

MOD = 10007
sys.setrecursionlimit(10**7)

cache = [[0]* 1001 for _ in range(1001)]
N,K = map(int,input().split())

def bino(n,k):
    if cache[n][k]: # 값이 있는경우 바로 값을 가져다쓴다.
        return cache[n][k]
    
    if k==0 or k==n:
        cache[n][k] = 1
    else:
        cache[n][k] = bino(n-1,k-1) + bino(n-1,k) # 10007 초과 할 수있음
        cache[n][k] %= MOD
    return cache[n][k]
    
print(bino(N,K))

 

반복문

MOD = 10007

cache = [[0]* 1001 for _ in range(1001)]
N,K = map(int,input().split())

# 이중 for문
for i in range(1001): # 한 행씩 값 차례로 넣어주기
    cache[i][0] = cache[i][i] = 1
    
    for j in range(1,i):
        cache[i][j] = cache[i-1][j-1] + cache[i-1][j]
        cache[i][j] %= MOD

print(cache[N][K])

---

# C++

 

재귀

#include <iostream>
#include <cstring>
using namespace std;

int N, K;
const int MAX = 1001;
int cache[MAX][MAX];
const int MOD = 10007;

int bino(int n, int k)

{
	if (n == k || k == 0) return 1;
	if (cache[n][k] != -1)
		return cache[n][k];
	return cache[n][k] = ((bino(n - 1, k) + bino(n - 1, k - 1)))%MOD;
}

int main()

{
	memset(cache, -1, sizeof(cache)); // 초기화
	cin >> N >> K;
	cout << bino(N, K) << endl;

	return 0;
}

 

반복문

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n,k;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> k;
	
	// n+1개 원소, 각 vector는 k+1개의 원소를 가지고 0으로 초기화
	vector<vector<int>> dp(n+1,vector<int>(k+1,0));
	
	for(int i=1;i<=n;i++){
	    for(int j=0;j<=k;j++){
	        if(j==0||i==j) dp[i][j] = 1;
	        else{
	            dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
	            dp[i][j]%=10007;
	        }
	    }
	}
	cout<<dp[n][k]<<'\n';
}