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

문제링크 : www.acmicpc.net/problem/9461

9461번: 파도반 수열

dp문제인데, dp문제를 거의 풀어본 적이 없어서 쉽지 않았다. 파도반 수열의 값 P(1) ~ P(11)의 값이 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12인데, 규칙을 찾으려 노력했지만 처음에는 잘 보이지 않았다. 여러가지 관찰을 하던 중 홀수 번째와 짝수 번째 파도반 수열로 나누어서 살펴보았다.

 짝수 번째 값들을 살펴보면 P(4) = P(1) + P(2), P(6) = P(3) + P(4), ..., P(n) = p(n-3) + p(n-2)이고, 홀수 번째 값들을 살펴보면 P(5) = P(2) + P(3), P(7) = P(4) + P(5), ..., P(n) = p(n-3) + p(n-2)이다. 따라서 n의 값이 홀수 짝수와 관계없이 P(n) = P(n-3) + P(n-2)이다. 

사실 이러한 규칙은 홀수 짝수 나누지 않고도 발견할 수 있지만 나누지 않았을 때는 찾지 못하였다.

이에 맞춰서 작성한 소스코드는 다음과 같다.

import sys

def padovan(d, n):
    if 1 <= n <= 3:
        return 1

    if d[n] != 0:
        return d[n]

    d[n] = padovan(d, n-3) + padovan(d, n-2)

    return d[n]


T = int(sys.stdin.readline())
d = [0 for _ in range(101)]
d[1], d[2], d[3] = 1, 1, 1

for _ in range(T):
    N = int(sys.stdin.readline())
    print(padovan(d, N))