[python/파이썬] 백준 11050 이항 계수1 / 11051 이항 계수 2

[문제 출처]

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

11050번: 이항 계수 1

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

11051번: 이항 계수 2

 

 

[#11050 소스 코드]

#11050

def fact(n):
  if n == 0 or n == 1:
    return 1
  else:
    return n * fact(n-1)
    
n, k = map(int, input().split())

print(int(fact(n)/(fact(k)*fact(n-k))))

 

[#11051 소스 코드]

 

이항 계수 1 문제와 같지만 범위가 1000으로 훨씬 크다.

따라서 위의 코드를 그대로 적용시키면 RecursionError가 뜨게 된다.

파이썬의 최대 재귀 깊이(1000) 보다 더 깊어지기 때문이다.

따라서 파스칼의 삼각형을 이용해 dp로 문제를 해결하였다.

파스칼의 삼각형을 모르더라도 몇 개 계산해보면 규칙 찾는 것은 어렵지 않다.

#11051 

n, k = map(int, input().split())

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

dp[1][0] = 1
dp[1][1] = 1

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

print(dp[n][k])