BOJ 9461: 파도반 수열- 파이썬(Python)

https://www.acmicpc.net/problem/9461

<접근 방법>

파도반 수열의 규칙을 찾는 문제이다. 아래 그림을 살펴보자.

파도반 수열의 진행 방식이다.

 
위의 그림을 처음부터 단계적으로 진행해 보면서 규칙을 찾아보자.

$P(1)=P(2)=P(3)=1$
$P(4)=P(1)+P(3)=2$
$P(5)=P(4)=2$
$P(6)=P(5)+P(1)=2+1=3$
...

 
위의 규칙을 살펴보면 다음의 규칙을 찾을 수 있다.

$P(N <= 0) = 0$
$P(N >= 5) = P(N - 1) + P(N - 5)$

 
따라서 1 ~ 4까지의 값은 먼저 fix한 다음 위의 공식을 적용하면 해결할 수 있다.
 

<소스 코드>

위의 코드를 이용한 전체 소스 코드 구현 결과이다.

import sys

n = int(sys.stdin.readline())

tri = [0 for _ in range(101)]
tri[1] = 1
tri[2] = 1
tri[3] = 1
tri[4] = 2

for i in range(n):
    k = int(sys.stdin.readline())
    for j in range(5, k + 1):
        if tri[j] == 0:
            st, ed = j - 5, j - 1
            if st <= 0:
                temp = 0
            else:
                temp = tri[st]
            if ed <= 0:
                temp2 = 0
            else:
                temp2 = tri[ed]
            tri[j] = temp + temp2
    print(tri[k])