백준 11051번 "이항 계수2"

문제

백준 11051번 이항 계수2

풀이

이항 계수1을 점화식을 통해 풀었다면, 이번에는 DP를 이용하여 풀어볼 것이다.

우선 파스칼의 삼각형을 알 필요가 있는데, 파스칼의 삼각형은 다음과 같은 형태이다.

첫번째 행은 n = 1일 경우이고, 내려갈 수록 n이 증가하는 형태이다.
각 행의 좌측, 우측 끝은 1로 값이 고정되어 있으며, 나머지는 바로 윗 행의 두 수의 합과 같다.
이를 이해하고 코딩을 하면 된다.

Python 코드

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
dp = [[0] for i in range(n+2)]

for i in range(1, n+2):
  for j in range(1, i+1):
    if j == 1 or 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)