[백준] 9095번 1, 2, 3 더하기

💡문제접근

• dp[0] = 0
• dp[1] = 1
• dp[2] = 2
• dp[3] = 4
• dp[4] = 7

• dp[4] 즉, 4를 1, 2, 3의 합으로 나타낼 수 있는 방법의 개수는 dp[1] + dp[2] + dp[3]의 합과 같다.
• 이를 점화식의 형태로 나타내면 dp[i] = dp[i-1] + dp[i-2] + dp[i-3]이다.

💡코드(메모리 : 30616KB, 시간 : 48ms)

T = int(input())
for _ in range(T):
    n = int(input())
    dp = [0, 1, 2, 4]
    for i in range(4, n+1):
        dp.append(dp[i-3] + dp[i-2] + dp[i-1])
    print(dp[n])

💡잘못된 코드

T = int(input())
for _ in range(T):
    n = int(input())
    dp = [0] * (n+1)
    dp[0], dp[1], dp[2], dp[3] = 0, 1, 2, 4
    for i in range(4, n+1):
        dp[i] = dp[i-3] + dp[i-2] + dp[i-1]
    print(dp[n])

• 틀린 이유 : 만약 n의 값이 1이나 2가 된다면 dp[3]은 존재할 수 없으므로 런타임에러(IndexError)가 출력된다.

💡소요시간 : 5m