[파이썬] 백준 11051번 이항 계수 2

11051번: 이항 계수 2

시간 제한

 1초

메모리 제한

256MB

문제

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

입력

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

출력

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

예제 입력 1 

5 2

예제 출력 1 

10

---

나의 풀이

• N과 K의 범위가 크기 때문에 중복된 계산을 줄이기 위해서 memoization을 이용했다.

import sys
sys.setrecursionlimit(10**6)

n, k = map(int, input().split())
memo = {0 : 1, 1 : 1}

def get_fact(n):
    if n in memo:
        return memo[n]
    else:
        memo[n] = n * get_fact(n - 1)
        return memo[n]

numerator = get_fact(n)
denominator = (get_fact(k) * get_fact(n - k))
print((numerator // denominator) % 10007)

---

다른 사람 풀이

• 이항 계수의 성질을 이용하여 DP로 풀었다.
• 이항 계수의 성질은 파스칼의 삼각형을 통해 확인할 수 있다.
• 알아두면 좋은 접근법인 거 같다.

n, k = map(int, input().split())
dp = [[0] * 1 for i in range(1001)]
dp[1].append(1)
for i in range(2, 1001):
    for j in range(1, i + 1):
        if j == 1:
            dp[i].append(1)
        elif j == i:
            dp[i].append(1)
        else:
            dp[i].append(dp[i - 1][j - 1] + dp[i - 1][j])
print(dp[n + 1][k + 1] % 10007)

[백준] 11051번(python 파이썬)

파스칼의 삼각형과 이항계수의 성질