[백준 11051] 이항 계수2

[BanApp]

import sys

a, b = map(int, sys.stdin.readline().split())
tmp = [1,1]
ans = []

if a == 1:
    print(1)

else:
    for _ in range(a - 1):
        ans.append(1)
        for i in range(1, len(tmp)):
            ans.append(tmp[i - 1] + tmp[i])
        ans.append(1)
        tmp = ans.copy()
        ans.clear()

    x = tmp[b] % 10007
    print(x)

조합을 쓰는 문제가 나온다면 파스칼 삼각형을 먼저 떠올려보자!

이런 삼각형이다. 제일 윗줄부터 1C0, 1C1, 2C0, 2C1, 2C2 ... 이렇게 나간다.
그리고 윗줄의 i-1 원소와 i번째 원소는 다음줄의 i번째 원소가 된다. 첫번째 원소와 마지막 원소는 무조건 1이다.
파스칼 삼각형을 전부 이차원 리스트로 만들면 테스트 케이스의 숫자가 커질때 너무 많기도 하고 그러니깐 tmp로 n-1번째 줄을 ans로 n번째 줄을 저장해서 이를 바꿔주면서 연산하면 최종적으로 1차원 리스트 tmp에 파스칼 삼각형의 n번째 줄이 담긴다. 이를 b로 인덱싱해서 aCb를 찾는다.
그리고 10007로 나눠 주면 끝! 만약 a가 1일 경우 답은 무조건 1이다. 따라서 a == 1을 만족하면 1출력!
내가 바로 전에 올렸던 다리놓기 문제에도 동일하게 적용이 가능하다.