[Python] 파도반 수열 [백준 9461]

문제 바로가기

풀이

• 다이나믹 프로그래밍을 활용하는 문제로
  입력값 N의 범위에 (1 ≤ N ≤ 100) 맞게 dp를 초기화 한다.
• n >= 6 부터 규칙이 나타나고 점화식을 세워 문제를 해결한다.

import sys

N = int(input())
dp = [0] * 101
dp[0] = 0
dp[1],dp[2],dp[3] = 1,1,1
dp[4],dp[5] = 2,2

i = 0
while i < N:
    
    n = int(sys.stdin.readline())
    if n < 6:
        print(dp[n])
    else:
        j = 6
        while j <= n:
            dp[j] = dp[j-1] + dp[j-5]
            j += 1
        print(dp[n])
    i += 1