[백준-9461] 파도반 수열 - 동적계획법 이용하기

#문제

 

#풀이

 점화관계에 주목하며 주어진 10개의 숫자에서 1,1,1,2,2,3,4,5,7,9에서 점화관계를 찾아보려고 노력했음. i의 값은 i-2 + i-3의 값과 같은 규칙을 찾을 수 있었다.

 

#코드

def answer(n) :
  if( n<= 3) :
    print(1)
    return
  list = [0 for i in range(n+1)]
  list[1] = 1
  list[2] = 1
  for i in range(3,n+1):
    list[i] = list[i-2] + list[i-3]
  print(list[n])



if __name__ == '__main__':
    times = int(input())
    for i in range(times):
      n = int(input())
      answer(n)