[백준/C++] 9461번 파도반 수열

문제: www.acmicpc.net/problem/9461

9461번: 파도반 수열

 

 

문제풀이

 

DP문제이다.

 

문제의 점화식

 

P[i] = P[i-5] + P[i-1]

 

주의할 점은 배열을 선언할 때 long long 형으로 선언해주어야 한다는 것이다. 처음 문제를 풀 때 int 형으로 선언하여 9%에서 계속 틀려서 헤매었다.

 

 

코드

#include <iostream>

using namespace std;

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int T;
    cin>>T;

    while(T--){
        long long N;
        cin>>N;

        long long p[101] = {1, 1, 1, 2, 2, 3, 4, 5, 7, 9}; //P[10] 까지는 문제에 명시 되어 있다.
        for(int i=10; i<N; i++){
            p[i] = p[i-5]+p[i-1]; //점화식
        }

        cout<<p[N-1]<<"\n"; //0부터 시작했으므로 인덱스에서 1을 빼준다.
    }

    return 0;
}

 

 

결과