Silver III 난이도의 파도반 수열 문제를 C++로 풀이한 내용입니다. 동적 계획법(Dynamic Programming)을 사용하여 주어진 점화식을 효율적으로 계산하는 방법을 설명합니다.

백준 9461: 파도반 수열

문제 소개

문제 번호: 9461
문제명: 파도반 수열
난이도 (티어): Silver III
사용 언어: C++
실행 시간: 0 ms
메모리: 2020 KB
문제 요약: 파도반 수열 $P (n)$ 은 다음과 같은 점화식을 따릅니다:
- $P (1) = 1$
- $P (2) = 1$
- $P (3) = 1$
- $P (n) = P (n - 1) + P (n - 5)$ (단, $n > 3$ )
  주어진 $n$ 에 대해 $P (n)$ 의 값을 계산하는 문제입니다.

접근 방법

이 문제는 주어진 점화식을 만족하는 수열의 값을 구하는 문제입니다. 수열의 값이 이전 항들의 값에 의해 결정되므로, 동적 계획법(Dynamic Programming, DP)을 활용하는 것이 가장 효율적입니다.

DP를 사용하면 같은 계산을 여러 번 반복하는 것을 방지하고, 이전에 계산된 값을 저장하여 재활용함으로써 시간 복잡도를 크게 줄일 수 있습니다. 문제에서 $n$ 의 최대값이 100이므로, 100개의 항까지의 값을 미리 계산해두고 쿼리에 대해 바로 응답하는 방식으로 접근했습니다.

풀이 과정

DP 배열 선언: dp라는 이름의 배열을 선언하여 $P (n)$ 의 값을 저장합니다. 문제에서 $n$ 의 최대값이 100이므로, 크기는 101로 충분합니다. long long 타입을 사용하여 수열 값이 커져도 오버플로우를 방지합니다.
초기값 설정 (Base Case): 문제에서 직접 주어진 $P (1), P (2), P (3)$ 의 값을 dp 배열에 초기화합니다. 추가적으로 $P (4)$ 와 $P (5)$ 의 값도 점화식을 이용해 미리 계산하여 초기값을 설정합니다.
- $P (1) = 1$
- $P (2) = 1$
- $P (3) = 1$
- $P (4) = P (3) + P (- 1)$ (점화식에 따라 $n > 3$ 일 때 적용되지만, $P (4)$ 의 경우 $P (4) = P (3) + P (4 - 5)$ 와 같이 인덱스가 음수가 되는 경우를 생각해야 합니다. 문제의 실제 점화식은 $P (n) = P (n - 1) + P (n - 5)$ 이며, 이는 $n = 4$ 일 때 $P (4) = P (3) + P (- 1)$ 이 됩니다. 하지만 문제의 Sample Test Case를 보면 $P (4) = 2, P (5) = 2$ 임을 알 수 있습니다. 이는 $P (n)$ 이 $n = 1, 2, 3$ 을 제외하고 $n - 1$ 과 $n - 5$ 를 더하는 점화식을 따르는 것이 아니라, $n = 1, 2, 3$ 까지는 1이고, $n = 4, 5$ 부터는 $P (n) = P (n - 1) + P (n - 5)$ 를 따르거나, 혹은 $P (n)$ 의 정의가 조금 더 확장된 형태로 해석될 수 있습니다. 주어진 코드에서는 $P (1) = 1, P (2) = 1, P (3) = 1, P (4) = 2, P (5) = 2$ 로 초기화한 후, $i = 6$ 부터 $d p [i] = d p [i - 1] + d p [i - 5]$ 를 사용합니다. 이는 주어진 풀이_코드에 명시된 방식으로, 이대로 따릅니다.)
점화식을 이용한 DP 채우기: $i$ 를 6부터 100까지 증가시키면서 dp[i] = dp[i-1] + dp[i-5] 점화식을 이용하여 dp 배열을 채워나갑니다.
쿼리 처리: 입력으로 주어지는 테스트 케이스의 수 $T$ 만큼 반복합니다. 각 테스트 케이스마다 정수 $n$ 을 입력받고, 미리 계산된 dp[n] 값을 출력합니다. ios::sync_with_stdio(false); cin.tie(nullptr);를 사용하여 입출력 속도를 최적화합니다.

핵심 아이디어:
수열의 정의를 파악하고, 중복 계산을 피하기 위해 DP 테이블을 미리 채워두는 것입니다. $P (n)$ 은 $P (n - 1)$ 과 $P (n - 5)$ 에 의존하므로, $P (1)$ 부터 $P (n)$ 까지 순차적으로 계산하면 됩니다.

주의할 점:

$n$ 이 100까지이므로 long long 타입을 사용하여 큰 수를 처리해야 합니다.
초기값 설정 시 문제의 정의를 정확히 따르거나, 제공된 코드의 초기값을 그대로 사용하는 것이 중요합니다. 본 코드는 $P (1 \dots 5)$ 를 명시적으로 설정하고 6부터 점화식을 적용합니다.

코드 설명

#include <bits/stdc++.h>
using namespace std;

int main() {
    // cin, cout의 속도를 최적화합니다.
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; // 테스트 케이스의 수를 입력받습니다.
    cin >> T;

    // dp[n] = n번째 파도반 수열의 값을 저장할 배열입니다.
    // 문제에서 n의 최대값이 100이므로, 101 크기로 선언하여 충분히 확보합니다.
    // long long 타입을 사용하여 큰 값을 저장합니다.
    long long dp[101];

    // --- 초기값 (base case) ---
    // 파도반 수열의 초기값들은 문제에서 직접 주어지거나,
    // 점화식의 적용을 위한 시작점으로 필요합니다.
    // 코드에서는 P(1)부터 P(5)까지 직접 값을 할당합니다.
    dp[1] = 1;
    dp[2] = 1;
    dp[3] = 1;
    dp[4] = 2; // P(4) = P(3) + P(-1) 와 같은 점화식이 직접 적용되지 않는 경우,
               // 문제의 샘플 값 또는 패턴에 따라 직접 설정합니다.
    dp[5] = 2; // P(5) = P(4) + P(0) 와 같은 점화식이 직접 적용되지 않는 경우,
               // 문제의 샘플 값 또는 패턴에 따라 직접 설정합니다.

    // --- 점화식 ---
    // P(n) = P(n-1) + P(n-5) 라는 점화식을 사용하여
    // dp 배열의 6번째 항부터 100번째 항까지 차례대로 계산합니다.
    for (int i = 6; i <= 100; i++) {
        dp[i] = dp[i-1] + dp[i-5];
    }

    // --- 쿼리 처리 ---
    // 미리 dp 배열에 모든 필요한 값을 계산해 두었으므로,
    // 각 테스트 케이스에 대해 입력받은 n에 해당하는 dp[n] 값을 바로 출력합니다.
    while (T--) {
        int n; // 계산할 파도반 수열의 항 번호 n을 입력받습니다.
        cin >> n;
        // 미리 계산된 dp[n] 값을 출력합니다.
        cout << dp[n] << "\n";
    }

    return 0;
}

복잡도 분석

시간 복잡도: O(100) = O(1)
- DP 테이블을 채우는 데는 100번의 연산이 필요합니다.
- 각 쿼리에 대한 응답은 O(1)입니다.
- $N$ 이 최대 100으로 고정되어 있으므로, 시간 복잡도는 상수 시간으로 볼 수 있습니다. (만약 $N$ 이 변수였다면 O(N)이 됩니다.)
공간 복잡도: O(100) = O(1)
- DP 테이블을 저장하기 위해 크기 101의 배열을 사용합니다.
- $N$ 이 최대 100으로 고정되어 있으므로, 공간 복잡도 역시 상수 공간으로 볼 수 있습니다. (만약 $N$ 이 변수였다면 O(N)이 됩니다.)

배운 점

이 문제를 통해 동적 계획법(DP)의 기본 개념과 활용법을 다시 한번 익힐 수 있었습니다. 특히, 다음과 같은 점을 배울 수 있었습니다.

DP 점화식의 중요성: 문제의 규칙성을 파악하여 재귀적인 관계(점화식)를 세우는 것이 DP 문제 해결의 핵심입니다.
Top-down vs. Bottom-up: 이 문제는 Bottom-up 방식 (작은 값부터 계산하여 큰 값을 구하는 방식)이 매우 효과적이었습니다. DP 테이블을 미리 채워두고 쿼리에 바로 응답하는 방식은 여러 번의 쿼리가 주어질 때 성능상 이점을 가집니다.
시간 및 공간 복잡도 최적화: $N$ 의 범위가 제한적일 때, DP 테이블을 미리 계산해두는 것이 각 쿼리마다 계산하는 것보다 훨씬 효율적임을 알 수 있었습니다.
기본값 설정의 중요성: DP 문제에서 초기값(Base Case) 설정은 매우 중요합니다. 문제의 정의를 정확히 이해하고, 점화식이 적용되기 위한 시작점들을 올바르게 설정해야 합니다. 이 문제에서는 $P (1)$ 부터 $P (5)$ 까지의 값을 명확히 정의하는 것이 중요했습니다.

이 문제는 간단한 점화식을 사용하지만, DP의 기본 원리를 충실히 적용하면 쉽게 해결할 수 있는 좋은 연습 문제입니다.