[SWEA 5256][Python] [파이썬 S/W 문제해결 최적화] 2일차 - 이항계수

코드

## SWEA 5256
T = int(input())
for test_case in range(1,T+1):
    n,a,b = map(int, input().split())
    dp = [[0]*(n+1) for _ in range(n+1)]
    t = min(a,b)

    for i in range(0, n+1):
        for j in range( min(i, t)+1 ) :
            if dp[i][j] == 0 :
                if j == 0 or j == i :
                    dp[i][j] = 1
                else :
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-1]

    print(f"#{test_case} {dp[n][t]}")

 

풀이

2차원 list dp에 2중 for 문을 돌면서 계수를 update한다. 

여기서 DP를 사용하기 위해서 이항계수의 성질을 이용하는데, 

(x+y)^2 = x^2 + 2*x*y + y^2 

(x+y)^3 = x^2 + 3*x^2*y + 3*x*y^2 + y^2

(x+y)^4 = x^2 + 4*x^3*y + 6*x^2*y^2 + 4*x^1*y^3 + y^4

위 예시들처럼 전체 식의 절반의 계수만 알면 되므로 이를 이용해 반복을 줄인다. 

첫번째 for문은 n까지, 두번째 for 문은 min(a,b)와 첫번째 for문의 index의 최소값 만큼만 반복하면 된다.