[백준 알고리즘] 이항계수2(11051)

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

이 문제를 풀기 위해서는 먼저 이항계수에 대해 알아야 합니다.

11050번 문제와는 달리 메모이제이션이라는 방법을 이용하여 풀어보겠습니다.

메모이제이션이라는 방법은 간단히 설명하면 메모를 해두어 메모가 되어있는 정보들은 바로 이용하는 방법입니다.

더 자세히 아시고 싶은 분은 나무위키를 참조하시기 바랍니다. 

(https://ko.wikipedia.org/wiki/%EB%A9%94%EB%AA%A8%EC%9D%B4%EC%A0%9C%EC%9D%B4%EC%85%98)

먼저 이항계수를 구하는 방법을 11050번 문제와 다른 공식을 이용하겠습니다.

$$n\mathbf{C}r = n-1\mathbf{C}r-1 + n-1\mathbf{C}r$$

위 공식을 이용할텐데 조금 더 자세하게 설명해보도록 하겠습니다.

파스칼의 삼각형을 보면 이해하기 쉽습니다.

위 삼각형에서 예시를 들어보겠습니다.

$$4\mathbf{C}2 = 3\mathbf{C}1 + 3\mathbf{C}2$$

원하는 값의 좌우측 상단을 더하면 된다는 것을 알 수 있습니다.

이것을 이용하여 파이썬 코드로 구현해보겠습니다.

fact = [[0 for i in range(1001)] for j in range(1001)]
fact[0][0] = fact[1][0] = fact[1][1] = 1
for i in range(2, 1001):
    for j in range(0, i+1):
        if i == j or j == 0:
            fact[i][j] = 1
        elif fact[i][j] == 0:
            fact[i][j] = fact[i-1][j-1] + fact[i-1][j]

fact라는 리스트에 이항계수 값들을 저장하겠습니다.

1001 X 1001 리스트를 0으로 초기화했습니다.

그 후 fact[0][0] fact[1][0] fact[1][1] 을 1으로 변경했습니다. 이 값들을 이용하여 재귀법으로 모든 값들을 구할 수 있습니다.

구해진 값들을 fact리스트에 저장을 하면 이후에 구하는 값들은 재귀하는 횟수가 줄어듭니다.

다만 이 방법은 메모리를 굉장히 많이 요구하는 방법입니다.

N, K = map(int, input().split())
print(fact[N][K] % 10007)

출력은 간단하게 fact리스트에 저장된 값들을 불러와 나머지를 구하는 것으로 마무리하면 되겠습니다.

fact = [[0 for i in range(1001)] for j in range(1001)]
fact[0][0] = fact[1][0] = fact[1][1] = 1
for i in range(2, 1001):
    for j in range(0, i+1):
        if i == j or j == 0:
            fact[i][j] = 1
        elif fact[i][j] == 0:
            fact[i][j] = fact[i-1][j-1] + fact[i-1][j]

N, K = map(int, input().split())
print(fact[N][K] % 10007)