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

파도반수열의 N번째 항을 구하는 문제이다.

접근 방법

점화식을 이용하여 푸는 문제라고 생각하여 규칙성을 찾으려고 노력을 하였다.

규칙성을 보다보니, 6번째 수열부터 규칙을 발견하였다

• 홀수번째 수열의 경우, 직전 짝수번째 + 전 전 짝수번째
• 짝수번째 수열의 경우, 직전 홀수번째 + 전 전 홀수번째

위 규칙을 적용하여 점화식은

• 5보다 큰 N에 대해 p(N) = p(n-1) + p(n-5) 로 구하였다.

n = int(input())


for i in range(n):
    x = int(input())
    if x < 6:
        dp = [0, 1, 1, 1, 2, 2]
        print(dp[x])
    else:
        dp = [0 for i in range(x+1)]
        dp[0:6] = [0, 1, 1, 1, 2, 2]
        j = 6
        while j < x+1:
            dp[j] = dp[j-1] + dp[j-5]
            j += 1
        print(dp[x])