[BOJ]11051. 이항 계수 2

문제:

자연수 N과 정수 K가 주어졌을 때 이항 계수 (N, K)를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N과 K가 주어진다. (1<=N<=1,000, 0<=K<=N)

출력:

(N, K)를 10,007로 나눈 나머지를 출력한다.

풀이 방법:

N의 크기가 커짐에 따라서 더 이상 이항계수 문제를 재귀적방법으로 해결할 수 없다. 일반적으로 재귀함수가 가독성이 좋긴 하지만 동일한 함수를 자주 호출하다보니 N이 커질수록 stack overflow가 발생할 수 있다. 따라서 이를 해결하는 방법으로 dp (메모리제이션) 을 사용한다. 작은 값의 함수들 부터 배열에 값을 저장하면서 원하는 값까지 진행을 하는 방식이다. 

따라서 이항계수1 문제와 풀이는 비슷하나 함수를 호출하는 것이 아닌 배열의 값을 호출한다는 차이가 있다.

a,b=map(int,input().split())
def bin2(n,k):
    b=[[0 for i in range(k+1)] for j in range(n+1)]
    for i in range(1,n+1):
        for j in range(min(n,k)+1):
            if (j==0 or j==i):
                b[i][j]=1
            else:
                b[i][j]=b[i-1][j-1]+b[i-1][j]
    return b[n][k]%10007
print(bin2(a,b))