[알고리즘] 동적 계획법(Dynamic Programming) - 백준 9461번 파도반 수열

정답 코드

def padovan(n):
  if n < 4:
    return 1
  
  cache = [0 for _ in range(n+1)]
  cache[0] = 1
  cache[1] = 1
  cache[2] = 1

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

N = int(input())
for _ in range(N):
  print(padovan(int(input())))

풀이과정

1 → 1 → 1 → 2 → 2 → 3 → 4 → 5 → 7 → 9

발견한 규칙
P(N) = P(N-2) + P(N-3)