백준 11050번 파이썬 _ 이항 계수 1

www.acmicpc.net/problem/11050

11050번: 이항 계수 1

문제유형 : DP, 수학, 구현

문제풀이 :

• 방법1. DP로 푸는방법 :
  • 이항계수는 k가 0일때 and n과 k가 같을때 1이고 나머지값에대해서는 n,k = n-1,k + n-1,k-1의 값을 갖는다.
  • 따라서 array[i][j] = array[i-1][j] + array[i-1][j-1] 의 점화식을 이용하면서 DP배열을 채워나가면 된다.
• 방법2 : 이항계수 공식으로 팩토리얼 라이브러리 이용
  • 공식 = n! / k! * (n-k)! 로 계산
  • math.factorial() 이용

정답코드 _ 방법1

import sys
input = sys.stdin.readline

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

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

for i in range(n+1):
    array[i][i] = 1
    array[i][0] = 1

for i in range(2,n+1):
    for j in range(1,n+1):
        if array[i][j] != 1:
            array[i][j] = array[i-1][j] + array[i-1][j-1]
            
print(array[n][k])

정답코드 _ 방법2

import sys
input = sys.stdin.readline

n,k = map(int, input().split())
import math
result = math.factorial(n) // (math.factorial(k) * math.factorial(n-k))
print(result)