9461번 파도반 수열

https://www.acmicpc.net/problem/9461

풀이: 문제 해결을 위한 전반적인 알고리즘 접근 방식

동적 계획법(Dynamic Programming) 접근 방식:

이 문제는 파도반 수열의 규칙을 찾아 점화식을 세우는 동적 계획법 문제로 분류할 수 있습니다. 주어진 수열의 초기 값들을 기반으로 다음 항을 유추하는 것이 핵심입니다.

세부 단계:

1. 상태 정의: dp[i]는 i번째 파도반 수열의 값을 나타냅니다. 문제에서 N의 최대값이 100이므로, dp 배열은 101의 크기를 가집니다.
2. 점화식: 주어진 수열을 분석하면 다음과 같은 규칙을 찾을 수 있습니다.
   • P(1) = 1
   • P(2) = 1
   • P(3) = 1
   • P(4) = 2 (P(1) + P(2) = 1 + 1 = 2) -> P(4) = P(2) + P(1)
   • P(5) = 2 (P(2) + P(3) = 1 + 1 = 2) -> P(5) = P(3) + P(2)
   • P(6) = 3 (P(3) + P(4) = 1 + 2 = 3) -> P(6) = P(4) + P(3) 따라서, 일반적인 점화식은 P(N) = P(N-2) + P(N-3) 입니다.
3. 초기 상태: 위 분석에 따라 dp[1] = 1, dp[2] = 1, dp[3] = 1로 초기화합니다.
4. 전이: i가 4부터 100까지 반복하면서 dp[i]를 dp[i-2] + dp[i-3]으로 계산하여 값을 채워 나갑니다.
5. 결과: 입력 N에 해당하는 dp[N] 값을 출력합니다.

시간 복잡도: O(MAX_N + T) 미리 100까지의 파도반 수열을 계산하는 데 O(MAX_N) 시간이 걸리고, 각 테스트 케이스마다 O(1)로 결과를 조회하므로, 총 시간 복잡도는 O(MAX_N + T)입니다. 여기서 MAX_N은 N의 최대값(100)이고, T는 테스트 케이스의 수입니다.

공간 복잡도: O(MAX_N) wave 벡터에 최대 101개의 long long 값을 저장하므로, N의 크기에 상관없이 상수 크기의 공간 O(MAX_N) (즉, O(1))을 사용합니다.

코드

9461.cpp

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int iter, N;
    cin >> iter;
    vector<long long> wave(101);
    wave[1] = 1LL;
    wave[2] = 1LL;
    wave[3] = 1LL; 
    for(int i = 4;i<=100;i++){
        wave[i] = wave[i-2] + wave[i-3];
    }
    while(iter--){
        cin >> N;
        cout << wave[N] << '\n';
    }
    return 0;
}

Standard Input (stdin): 2 6 12

⏳ Running... C++