[백준/파이썬] 11051번: 이항 계수 2

문제

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

풀이

• 이항 계수
• 파스칼 삼각형을 활용한 DP 문제

파스칼 삼각형을 2차원 리스트로 구현하여 문제를 해결하면 됩니다.

파스칼 삼각형이란?

이항계수를 삼각형 형태로 배열한 구조

1. 맨 위(0번째 행)는 1
2. 각 행의 첫 번째와 마지막 원소는 1
3. 나머지 원소는 바로 위의 두 원소를 더한 값

이러한 파스칼 삼각형의 특성을 가지고 점화식을 작성하면 됩니다.
2번째 특성에 의해 모든 숫자는 1로 초기화 해주어야 합니다.

dp = [[1]*(n+1) for _ in range(n+1)]

2번째 행부터 계산을 시작하면 되기 때문에 for문은 2부터 n+1까지 계산을 진행합니다.
그리고 각 행의 첫 번째와 마지막 원소는 1이기 때문에 2번째 for문은 1부터 i까지 계산을 진행해주면 됩니다.

for i in range(2,n+1):
    for j in range(1,i):
        dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

코드

import sys
input = sys.stdin.readline

n,k = map(int,input().split())
dp = [[1]*(n+1) for _ in range(n+1)]

for i in range(2,n+1):
    for j in range(1,i):
        dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

print(dp[n][k] % 10007)