백준 알고리즘 11051번 이항 계수 2(python)

이항 계수 1 문제처럼 그냥 factorial 함수를 사용해서 풀어도 된다.

import math
n1, n2 = map(int, input().split())
ans = math.factorial(n1) // math.factorial(n1-n2) // math.factorial(n2) 
print(ans%10007)

알고리즘 분류가 다이나믹 프로그래밍인 것을 보아하니 파스칼의 삼각형을 사용해서 풀어보라는 것 같아서

구현해봤는데 위에 방법보다 훨씬 느리다. factorial 사용 56ms < 파스칼의 삼각형 424ms -> 거의 8배 차이

그냥 파스칼의 삼각형이라는 것이 무엇인지 정도만 알고 지나가면 될 문제 같다.

li = [[0 for i in range(1001)] for j in range(1001)]
li[0][0] = li[1][0] = li[1][1] = 1
for i in range(2, 1001):
    for j in range(i+1):
        if j == 0 or i == j:
            li[i][j] = 1
        else:
            li[i][j] = li[i-1][j-1] + li[i-1][j]
n1, n2 = map(int, input().split())
print(li[n1][n2] % 10007)