점화식이다? 그럼 일단 DP를 생각해보자.

9095:1,2,3 더하기

1. 내 풀이 1: 성공

import sys

T = int(sys.stdin.readline())
cnt = 0

while T != cnt: 
    n = int(sys.stdin.readline())
    dp = [0] * (n+3)

    dp[1] = 1
    dp[2] = 2
    dp[3] = 4

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

    print(dp[n])
    cnt +=1

DP 문제를 풀면서 깨달은 바는,

점화식 = 일단은 DP

라고 생각해보자는 것이다.

이번 문제 역시 점화식을 발견(만 한다면) 하면 쉽게 풀리는 문제이다.

• n=1일 때 1
• n=2일 때 2
• n=3일 때 4
• n=4일 때 7
• n=5일 때 14
• n=6일 때 28

등의 규칙으로 이루어진다. 이에 대한 점화식은

n의 방법 = (n-1)의 방법 + (n-2)의 방법 + (n-3)의 방법

인 것을 확인할 수 있다.

2. 다른 풀이

(출처: https://pacific-ocean.tistory.com/192)

t = int(input())
ott = [1, 2, 4]
for i in range(3, 10):
    ott.append(ott[i - 3] + ott[i - 2] + ott[i - 1])
for i in range(t):
    n = int(input())
    print(ott[n - 1])

항상 풀이가 깔끔하다고 생각되는 깨지고 부서져라님의 풀이이다.
나는 DP 문제를 풀 때 항상 DP 리스트를 선언했는데 이런 식으로 append 하는 방법도 있다는 것을 새로이 알게 되었다!

오늘도 신기한 알고리즘의 세계 끝~!