처음 푼 코드

import sys

input = sys.stdin.readline

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

def factorial(num):

    count = 1

    for i in range(num, 1, -1):
        count *= i

    return count

n_fac = factorial(n)
k_fac = factorial(k)
nk_fac = factorial(n-k)

print((n_fac // (k_fac * nk_fac)) % 10007)

이항 계수 공식을 찾아서 그대로 적용했는데 성공했다. 근데 이렇게 푸는게 아닌 것 같다..
이게 무슨 DP야..

이항 계수가 무엇일까?

이항계수(Binomial Coefficient)는 조합론에서 등장하는 개념으로 주어진 크기 집합에서 원하는 개수만큼 순서없이 뽑는 조합의 가짓수를 일컫는다. 2를 상징하는 ‘이항’이라는 말이 붙은 이유는 하나의 아이템에 대해서는 ‘뽑거나, 안 뽑거나’ 두 가지의 선택만이 있기 때문이다.

메모리얼을 적용한 DP로 푼 코드

N, K = map(int, input().split())

memory = [[0 for _ in range(N+1)]
          for _ in range(N+1)]  # 파스칼의 삼각형을 만들기 위한 리스트 초기화

for n in range(0, N+1):
    for i in range(0, N+1):
        if i == 0: # 첫번째 -> 하나도 선택하지 않았을 경우
            memory[n][i] = 1

        elif i == n: # 마지막 -> 모두 선택했을 경우
            memory[n][i] = 1

        else:
            memory[n][i] = memory[n-1][i-1] + memory[n-1][i]

print(memory[N][K] %10007)

첫번째 코드는 공식을 사용해서 푼 코드인데 비효율적이다. 이번에는 DP로 파스칼의 삼각형을 만들어주어서 풀었다.