📌 [BOJ] 백준 9461 파도반 수열

📖 문제

📖 예제

📖 풀이

import sys

T = int(input())

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

수의 나열을 보고 점화식만 찾으면 간단한 문제이다.
주의할 점은 dp 배열을 만들 때 0 x (n+1)으로 할 경우이다.
dp[1], dp[2], dp[3]을 지정해야하기 때문에 위와 같이 배열을 만들 경우 n이 2일 경우 dp[3]에 대한 index가 없어 오류가 발생한다.