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

 

• 문제 

---

 

• 잘못된 풀이

T = int(input())

for i in range(0, T):
    n = int(input())
    dp = [0] * n

    dp[0] = 1
    dp[1] = 2
    dp[2] = 4

    for j in range(3, n):
        dp[j] = dp[j-1] + dp[j-2] + dp[j-3]
    print(dp[n-1])

 

해당 문제는 n=1일 때, 1 / n=2일 때, 2 / n=3일 때, 4 / n=4일 때, 7 / n=5일 때, 13 / n=6일 때, 24이다. 

dp를 n만큼 초기화하여 문제 풀이를 시도했다.

런타임 에러(IndexError)로 문제풀이에 실패했다. 

 

 

 

• 올바른 풀이

T = int(input())

def dfs(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    elif n == 3:
        return 4
    else:
        return dfs(n-1) + dfs(n-2) + dfs(n-3)

for i in range(T):
    n = int(input())
    print(dfs(n))

 

다음과 같이 함수로 문제 풀이를 시도했다.

매번 n을 새로 받아서 dp의 길이를 지정하는 것이 아니라, 함수로 풀이하며 return으로 해결하고자 했다.