[BOJ 9461] 파도반 수열

문제 요약

파도반 수열 P(N)이 주어졌을 때, 각 테스트 케이스마다 P(N)을 출력한다.

• T개의 테스트 케이스
• 1 ≤ N ≤ 100

초기 값은:

• P(1)=1, P(2)=1, P(3)=1, P(4)=2, P(5)=2

이후 점화식은:

• P(n) = P(n-5) + P(n-1) (n ≥ 6)

내가 푼 방식

이 문제는 규칙(점화식)만 찾으면 DP로 쉽게 풀린다.

• N의 최댓값이 100이므로,
• 미리 P(1) ~ P(100)까지 전부 구해두고,
• 각 테스트 케이스는 O(1)로 출력한다.

내 코드

p = [1, 1, 1, 2, 2]

for i in range(5, 101):
    p.append(p[i - 5] + p[i - 1])

t = int(input())

for x in range(t):
    n = int(input())
    print(p[n - 1])

이번 문제로 정리한 포인트

• DP 문제는 “점화식 + 초기값”만 정확히 잡으면 구현이 단순해진다.
• 여러 테스트 케이스가 있을 때는, 최대 범위까지 미리 전처리(precompute) 해두면 빠르고 깔끔하다.
• 인덱스가 0부터 시작하는 파이썬 리스트에서는 P(n)을 p[n-1]로 맞춰두면 편하다.