[Baekjoon] 9461번 : 파도반 수열

실버 3

9461번: 파도반 수열

 

문제 풀이

파도반 수열의 규칙을 찾아보면 다음과 같다. 

n = 1 -> 1
n = 2 -> 1
n = 3 -> 1
n = 4 -> 2
n = 5 -> 2
n = 6 -> 3 (f(1)+f(5))
n = 7 -> 4 (f(2)+f(6))
n = 8 -> 5 (f(3)+f(7))
n = 9 -> 7 (f(4)+f(8))
n = 10 -> 9 (f(5)+f(9))

5까지는 규칙이 없지만 6부터 규칙이 나타난다.

즉 n이 5보다 클때 다음 점화식을 만족한다. 

dp[i] =dp[i-5] + dp[i-1]

 

코드

t = int(input())
fix_value = [0, 1, 1, 1, 2, 2]

for _ in range(t):
    n = int(input())
    p = [0] * (n + 1)

    if n > 5:
        p[0:6] = fix_value
        for i in range(6, n+1):
            p[i] = p[i-5] + p[i-1]
    else:
        for i in range(1, n+1):
            p[i] = fix_value[i]

    print(p[n])