[python] 9095: 1, 2, 3 더하기

1, 2, 3 더하기

DP문제에 익숙해지는 중이다. 처음에 봤던 나는 "이걸 어떻게 다 하나씩 구하지🫡 조합으로 풀어야 하나... 답이 없는데" 이러고 있었다.

코드 설명

DP	#1	#2	#3	#4	#5	#6	#7	#8	#9	#10	#11
DP[1]	1
DP[2]	1+1
-	2
DP[3]	1+1+1	2+1
-	1+2
-	3
DP[4]	1+1+1+1	2+1+1	1+2+1	3+1
-	1+1+2	2+2
-	1+3

DP[2] = (DP[1] + 1) = 1이 되는 방법 + 1
DP[3] = (DP[2] + 1) + (DP[1]+2) = (2가 되는 방법 + 1) + (1이 되는 방법 + 2) = 3이 되는 방법
DP[4] = (DP[3] + 1) + (DP[2] + 2) + (DP[1]+3)

코드

import sys
input = sys.stdin.readline

DP = [0] * 11
DP[1], DP[2], DP[3] = 1, 2, 4
testcases = int(input().rstrip())


def getWays(target: int) -> int:
    for index in range(4, target+1):
        DP[index] = DP[index-1]+DP[index-2]+DP[index-3]

    return DP[target]


for _ in range(testcases):
    num = int(input().rstrip())
    print(getWays(num))

참고 자료

바킹독 블로그 - DP