백준 11051번 이항 계수 2

정보

문제 바로가기 [클릭]

난이도: Silver1

관련 개념: #수학 #정수론 #다이나믹 프로그래밍

---

조건

시간 제한	메모리 제한
1 초	256 MB

---

문제

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

---

입력

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

---

출력

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

---

예제 입출력 1

입력

5 2

출력

10

---

코드(파이썬)

import sys

sys.setrecursionlimit(10**6)

def pascal(n, k):
    if (n, k) in combs:
        return combs[(n, k)]
    else:
        result = (pascal(n-1, k-1) + pascal(n-1, k)) % 10007
        combs[(n, k)] = result
        combs[(n, n-k)] = result
        
        return result
        
n, k = map(int, input().split())

combs = dict(zip([(i, 0) for i in range(1, n+1)]+[(i, i) for i in range(1, n+1)], [1 for _ in range(1, n+1)]+[1 for _ in range(1, n+1)]))
result = pascal(n, k)

print(result)

---

특이사항

• 파스칼의 삼각형을 이용했으나 다이나믹 프로그래밍을 통해 해결 가능
• 아직 다이나믹 프로그래밍에 대한 개념 부족
• 내 코드(71,244KB, 272ms)에 비해 우수한 코드(바로가기, 30,864KB, 68ms)와 비교

  • n, k = map(int, input().split())
    
    if k==0 or k==n:
        print(1)
    else:
        if 2*k>n:
            k=n-k
        dp=[1]*(k+1) # k번째 항 : nCk (0항~k항)
        dp[1]=n
        for i in range(2,k+1):
            dp[i]=(dp[i-1]*(n+1-i))//i
        print(dp[k]%10007)
    

---

참고문헌

-