[백준 11050, 11051][파이썬] 이항 계수

11050번과 11051번은 문제에서 주어지는 입력 값의 범위만 다르고 똑같은 문제이다.

 

11051번 문제를 기준으로 풀이해보려한다.

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

11051번: 이항 계수 2

이항 계수 풀이법은 두 가지로 나뉜다.

 

1. 반복문 사용

모두 알다시피 조합을 구하는 식은 아래와 같다.

$$ nCr =\frac{nPr}{r!} $$

이렇게 반복문을 사용하여 조합을 구하는 방법이 있다.

 

<반복문 사용 코드>

import sys
n, k = map(int, sys.stdin.readline().split())
res=1
for i in range(k):
    res=res*(n-i)
for i in range(1,k+1):
    res=res//i
print(res)

 

2. 파스칼의 삼각형 사용

파스칼의 삼각형은 조합, 즉 이항 계수를 삼각형으로 나타낸 모습이다.

https://ko.wikipedia.org/wiki/%ED%8C%8C%EC%8A%A4%EC%B9%BC%EC%9D%98_%EC%82%BC%EA%B0%81%ED%98%95

위를 수식으로 나타내면 아래와 같다.

$$ nCr=(n-1)C(r-1)+(n-1)Cr $$

 

파스칼의 삼각형을 사용하면 이 문제는 동적 계획법(dynamic programming) 문제가 된다.

 

이중 리스트로 모든 이항 계수의 값을 구한 다음 문제를 풀 수 있다.

 

<파스칼의 삼각형 사용 코드>

import sys
n, k = map(int, sys.stdin.readline().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)