백준 알고리즘 - 1, 2, 3 더하기 (9095번) [Python]

문제

문제 상황

- 더하는 순서에 따라 같은 숫자의 조합이여도 다르게 인식된다. 

- itertools 의 permutation을 하기엔 케이스가 너무 커진다. 

 

해결 전략

- 피보나치의 점화식이 되므로 동적프로그래밍을 이용해 Bottom - up으로 해결한다. 

코드 

t = int(input()) # testcase
tc = []
def p123(n):
    dp = [0,1,2,4]
    for i in range(4,n+1):
        dp.append(dp[i-1]+dp[i-2]+dp[i-3])
    return dp[n] 
for _ in range(t):
    tc.append(int(input()))
for i in range(t):
    print(p123(tc[i]))

 

해설

새로 학습한 것 & 실수

- 한정된 도구를 이용해 더한 결과를 출력해내는 것에서 피보나치를 연상한다. ( ex) 01타일 )

- 피보나치를 해결하기 위해 Bottom-Up의 DP를 해결 도구로 한다.