백준 9461 파도반수열

문제

---

솔루션

import sys
input = sys.stdin.readline
arr = [0 for i in range(101)]

arr[1]=1
arr[2]=1
arr[3]=1

for i in range(4,101):
    arr[i]=arr[i-3]+arr[i-2]

t = int(input())
for i in range(t):
    n = int(input())
    print(arr[n])

---

깨달은 점

다이나믹 프로그래밍(dp) 문제로 점화식을 구해서 풀어야 했다.

n번째 정삼각형의 변의 길이는 (n-2)번째 삼각형과 (n-3)번째 삼각형의 변의 길이의 합과 같아서 점화식을 구하면

 

f(n)=f(n−2)+f(n−3) (단,n=1,2,3일때f(n)=1) 이다.

이를 이용해 dp의 메모제이션을 활용하면 된다.