테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 파도반 수열 ======

===== 풀이 =====
  * 간단한 1차원 DP. 그림을 잘 보면 P(n) = P(n-1) + P(n-6) 의 점화식을 쉽게 발견할수 있다.
  * 선형점화식이므로 n번째 항의 값을 O(logn)에 계산하는 것도 가능하지만, 문제에서 주어지는 n의 범위가 최대 100으로 매우 작고 여러개의 쿼리를 처리해야 하므로, 그냥 P(1)~P(n)을 O(n)에 구해두고 쿼리마다 값을 출력하는 것이 더 낫다.
  * [[ps:벌러캠프-매시 알고리즘]]을 공부할때 이 문제를 연습문제로 사용했었는데, 점화식의 계수가 1,0,0,0,0,1 이 아니라 1,1,0 으로 나와서 구현이 잘못된줄 알고 한참 삽질한적이 있다.. 알고보니 파도반 수열의 점화식은 P(n) = P(n-2) + P(n-3) 으로 쓰는것도 가능했다.. (사실 이게 더 일반적)
  * 문제와는 관계 없지만 파도반 수열에는 여러가지 특징이 있긴 하다. [[wk>Padovan sequence]] 참고.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 9461. 파도반 수열".

- Problem link: https://www.acmicpc.net/problem/9461
- Solution link: http://www.teferi.net/ps/problems/boj/9461

Tags: [DP]
"""


def main():
    T = int(input())
    N = [int(input()) for _ in range(T)]
    dp = [None, 1, 1, 1, 2, 2]
    for _ in range(6, max(N) + 1):
        dp.append(dp[-1] + dp[-5])
    for x in N:
        print(dp[x])


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:실버_3}}