[BOJ] 백준 9095번 1,2,3 더하기 (python)

 

 

Dynamic Programming을 이용한 풀이.

 

점화식은 아주 간단하게 유도 가능하다.

n을 1,2,3의 합으로 나타내는 방법의 수를 출력한다.

dp[n] = dp[n-1] + dp[n-2] + dp[n-3]

dp[n-1] 은 +1, dp[n-2] 은 +2, dp[n-3] 은 +3의 합으로 나타내는 방법의 수라고 생각하면 된다.

(중복 x, 최소o)

 

초항은 dp [1] = 1, dp[2] = 2, dp[3] = 4

 

소스코드는 다음과 같다.

n = int(input())

dp_list = [0, 1, 2, 4]

for _ in range(n):
    num = int(input())
    if num > len(dp_list)-1:
        for i in range(len(dp_list), num+1):
            dp_list.append(0)
            dp_list[i] = dp_list[i-1] + dp_list[i-2] + dp_list[i-3]

    print(dp_list[num])