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

🥚문제

---

🥚입력/출력

---

🍳코드

import sys
input = sys.stdin.readline

n, k = map(int, input().split())

# 파스칼의 삼각형 이용
#dp[n][k] = nCk
dp = [[0]*(n+1) for _ in range(n+1)]
dp[0][0] = 1

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

print(dp[n][k])

---

🧂아이디어

DP

이항계수 - 정의

이항계수 - 파스칼의 삼각형

• 이항계수를 삼각형 모양의 표에 늘어놓은 것을 파스칼의 삼각형이라고 한다.
• 이를 활용하면 dp로 문제를 쉽게 풀 수 있다.
• 파스칼의 삼각형을 2차원 리스트로 나타내면

  dp = 
  [[1, 0, 0, 0, 0, 0]
  [1, 1, 0, 0, 0, 0]
  [1, 2, 1, 0, 0, 0]
  [1, 3, 3, 1, 0, 0]
  [1, 4, 6, 4, 1, 0]
  [1, 5, 10, 10, 5, 1]]

  • dp[ i ][ j ]는 C(i, j)를 나타낸다
  • dp[ i ][ j ] = dp[ i-1 ][ j-1 ] + dp[ i-1 ][ j ]이라는 규칙성을 갖는다
  • j == 0이거나 j == i일 때는 dp[ i ][ j ] = 1

출처
이항 계수 - 위키피디아
파스칼의 삼각형 - 위키피디아