[백준 9461번] 파도반 수열 - python

문제 링크

https://www.acmicpc.net/problem/9461

9461번: 파도반 수열

풀이

- dp 문제

규칙을 찾아보니, 

n이 1 ~ 3일 때 : dp[i] = 1

n이 4일 때 : dp[i] = 2

n이 5부터 : dp[i] = dp[i-5] + dp[i-1]

따라서 index1 은 0부터 시작 index 2는 4부터 시작하여 하나씩 증가하면서 dp 값 찾아주었다. 

t = int(input())

for _ in range(t):
  
  n = int(input())
 
  if n <= 3 :
    print(1)
  elif n == 4:
    print(2)
  else :
    dp = [0] * (n+1)

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

    index1 = 0 
    index2 = 4

    for i in range(5,n+1):
      dp[i] = dp[index1] + dp[index2]
      index1 += 1 
      index2 += 1
    
    print(dp[n])