[ BOJ ] 11051 : 이항 계수 2 ( SILVER 2 ) / Python

>> 문제 바로가기 (https://www.acmicpc.net/problem/11051)

 

풀이 과정

import sys
import math
input = sys.stdin.readline

n, k = map(int, input().rstrip().split())
print(math.comb(n, k)%10007)

파이썬은 math.comb 를 사용해도 되지만... 이 문제가 실버 2인 이유가 있으므로 다른 방식으로도 풀이해보자.

 

 

출처 : https://wikidocs.net/155598

해당 문제는 파스칼의 삼각형 모양을 떠올리면 쉽게 풀이할 수 있다.

파스칼의 삼각형은 바로 위의 왼쪽 수와 오른쪽 수를 더한 값이므로, 이를 DP 점화식으로 활용하여 풀이한다.

 

import sys
input = sys.stdin.readline

n, k = map(int, input().rstrip().split())
dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
dp[0][0] = 1
dp[1][0] = 1
dp[1][1] = 1

for i in range(2, n+1):
    for j in range(n+1):
        if j == 0 or j == n: dp[i][j] = 1
        else: dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % 10007

print(dp[n][k])