[DP] 백준 #11051 이항계수 2 - Python

🗂️ 문제

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

 

 

💡 접근법

이항 계수란 그냥 조합이다. 즉, (5, 2)란 5C2를 구하는 것이다.

이항계수의 성질을 이용하여 동적계획법으로 문제를 풀었으며, 이항계수의 성질은 다음과 같다.

 

1. nCk = nCn-k
2. nCk = n-1Ck + n-1Ck-1

파스칼의 삼각형을 본다면 더 쉽게 이해가 가능할 것이다.

 

 

위 두 성질을 기반으로 세운 DP 점화식은 다음과 같다.

dp[i][k] = dp[i-1][k] + dp[i-1][k-1] (i≥1, k≥1)

 

추가적으로 코드에서는 1번 성질을 이용해서 for문의 반복횟수를 줄일 수 있다.

예시로, 5C2 == 5C3이므로 5//2까지만 순회한다면 5에 대한 모든 조합의 경우를 구할 수 있다.

5C0 == 5C5, 5C1 == 5C4, 5C2 == 5C3이기 때문이다.

 

6의 경우도 6C3까지만 순회한다면 모든 경우를 구할 수 있다.

6C0 == 6C6, 6C1 == 6C5, 6C2 == 6C4이기 때문이다.

 

😎 내 코드

import sys

N, K = map(int, sys.stdin.readline().split())
dp = []
for i in range(N+1):
    dp.append([1 for _ in range(i+1)])

for i in range(2, N+1):
    for k in range(1, (i)//2+1):
        dp[i][k] = dp[i][i-k] = (dp[i-1][k] + dp[i-1][k-1]) % 10007

print(dp[N][K])

 

🧐 배운 점

• 이항계수 == 조합
• 이상계수의 성질
  1. nCk = nCn-k
  2. nCk = n-1Ck + n-1Ck-1

 

✅ 정답 확인