문제 출처 : https://www.acmicpc.net/problem/9461

---

문제 파악

이 문제는 규칙을 찾기만 하면 매우 간단한 DP 문제다. 처음에는 점화식이 바로 보이지 않아서 직접 수열을 하나씩 적어보며 규칙을 만들어 갔다.

---

규칙 찾기

처음 몇 항을 직접 계산해보면 다음과 같은 패턴이 나온다.

• P(1) = 1
• P(2) = 1
• P(3) = 1
• P(4) = 2
• P(5) = 2
• P(6) = P(5) + P(1) = 3
• P(7) = P(6) + P(2) = 4
• P(8) = P(7) + P(3) = 5
• P(9) = P(8) + P(4) = 7
• ...

살펴보면 6번째 항부터 일정한 규칙이 나타난다.

핵심 점화식

P(N) = P(N-1) + P(N-5)

즉, 바로 이전 항과 다섯 번째 전 항의 합이 된다.

---

DP 배열 크기 주의

입력되는 N은 최대 100이므로, 매 테스트케이스마다 dp[1] ~ dp[N]을 초기화하려다 보면 범위를 넘겨서 IndexError가 발생할 수 있다. 이를 예방하기 위해서는 애초에 dp 배열을 충분히 크게 선언해두는 방식이 안정적이다.

그래서 dp를 [0] * 101로 선언했다. (0~100까지 사용 가능)

---

최종 코드

import sys
input = sys.stdin.readline

T = int(input())

for _ in range(T):
    N = int(input())

    dp = [0] * 101
    
    dp[0] = 0
    dp[1], dp[2], dp[3] = 1, 1, 1
    dp[4], dp[5] = 2, 2
    
    for j in range(6, N + 1):
        dp[j] = dp[j - 1] + dp[j - 5]
    
    print(dp[N])

---

이 문제의 포인트는 규칙을 직접 관찰하는 과정과, 작은 N에 대해 인덱스 오류가 나지 않도록 dp 배열을 넉넉하게 선언하는 것이다. 점화식을 한 번만 발견하면 매우 간단하게 해결된다.