백준 22.03.20. 11051번 - 이항 계수2

---

from math import factorial


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

print((factorial(N)//(factorial(K)*factorial(N-K))) % 10007)

이항계수를 구하여 바로 10007로 나누어줘도 정답처리가 됩니다.

하지만 문제 아랫쪽 알고리즘 분류에 다이나믹 프로그래밍이 있으니 dp를 사용해봅시다.

 

---

파스칼의 삼각형의 처음 5줄 // 위키백과

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

dp = [[0]for i in range(N+2)]

dp[1].append(1)

for i in range(2, N+2):
    for j in range(1, i+1):
        if j == 1:
            dp[i].append(1)
        elif 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)

• 위 그림에서 파스칼의 삼각형을 중첩리스트 dp로 가정하고 (a+b)의 0제곱~5제곱까지 표현했다고 한다면
• (a+b)의 n 제곱의 단항식에서 1번째와 n번째 이항계수는 1이며 그 사이의 k의 이항계수는 dp[n-1][k-1]+dp[n-1][k]가 됩니다.
• 이것을 이용하여 코드를 작성해줍시다.
• 우선 dp리스트의 길이는 필요한 만큼인 0~N+1까지 나올 수 있도록 범위를 지정해줍니다.
• 그리고 예외라고 할 수있는 (a+b)의 0제곱인 dp[1]은 직접 할당해줍니다.
  • dp의 요소들은 [0, 1, n, ...., 1] 형식을 갖습니다.
  • 따라서 dp[0] = [0], dp[1] = [0,1]이므로 예외로 간주하고 이항계수 nCk를 구하는 코드에서 n을 담당할 i 를 2부터 시작합니다.
  • dp의 요소들이 의미없는 0부터 시작하기 때문에 j 는 1부터 시작합니다.
• j 가 처음이거나 맨 마지막일 때, 계수는 1이므로 직접 추가해줍니다.
• 그 사이라면 계산하여 할당해야 하기때문에 dp[i-1][j-1]+dp[i-1][j]를 할당해줍니다.
• 파스칼의 삼각형을 필요한 만큼 구했으니 이것을 바탕으로 출력해줍니다.
  • dp[0] = [0]이며, dp[n][0] = 0이기 때문에 인덱스를 모두 +1씩해줍니다.