백준(Backjoon) 11051번 : 이항 계수 2 - python 풀이

❓백준(Baekjoon) 11051번 : 이항 계수 2

📈 문제 요약

자연수 N, K가 주어질 때 이항 계수 (N, K)를 구하면 되는 문제

🤨 접근법

우리가 익히 알고 있는 이항 계수를 구하면 되는 문제이다. 조합의 수와 관련되어 있기에 파이썬의 itertools의 Combinations를 활용해 조합의 개수를 구할까도 생각해봤지만, 이항 계수의 경우 특정 규칙이 있는 것을 알고 있었기 때문에 점화식을 세워 DP로 접근할 수 있었다.

위와 같이 이항계수를 4개의 행 까지만 나열하면 오른쪽에 있는 형태와 같은데, 각 행의 첫 번째와 마지막 원소는 1이며, 그 사이의 수는 그 바로 위 행의 두 수의 합임을 직관적으로 확인할 수 있다.

따라서 점화식을 세우면, 아래와 같다.

이를 코드에 그대로 반영해 이항 계수(n, k)를 dp배열의 마지막 행의 k번째 원소를 참조해 얻어낼 수 있다.

🔡 코드

import sys

input = sys.stdin.readline

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

dp = [[1 for _ in range(n)] for n in range(2, N+2)]

for n in range(1, N):                        
    for k in range(1, n+1):                      
        dp[n][k] = dp[n-1][k-1]+dp[n-1][k]
        

print(dp[N-1][K] % 10007)

Tip. 이항 계수 행렬의 첫 번째 행이 2개의 요소를 가지면서 시작함에 유의하며 dp 배열을 선언해야하며, 이에 따른 Index Error가 발생하지 않게 집중하자. 음주 후 문제를 풀어서 많이 꼬였었다…