알고리즘 - Python / 백준 - 9461번 : 파도반 수열

9461번: 파도반 수열 (acmicpc.net)

9461번: 파도반 수열

 

---

풀이

• DP 문제이므로 점화식을 먼저 찾는다
• 점화식을 찾기위해 해당되는 수열을 처음 부터 나열하여 규칙을 찾아본다
• DP[i] = DP[i-1] + DP[i+5] 라는 점화식을 찾았으므로 이를 통해 전체 DP 배열을 구하고 답을 내면 된다

 

import sys

stack = [0,1, 1, 1, 2, 2, 3, 4, 5, 7, 9 ]


for i in range(11,101):
  stack.append(stack[i-1] + stack[i-5])


n = int(sys.stdin.readline())
for _ in range(n):
  m = int(sys.stdin.readline())
  print(stack[m])

---