Beakjoon 9461 파도반 수열

23 Feb 2021 in Algorithm

문제 링크 : https://www.acmicpc.net/problem/9461

나의 풀이

수열을 처음부터 나열해 보면 패턴을 찾을 수 있다.
P(1) = 1
P(2) = 1
P(3) = 1
P(4) = 1+1 = 2
P(5) = 1+1 = 2
P(6) = 2+1 = 3
P(7) = 2+2 = 4
P(8) = 3+2 = 5
P(9) = 3+4 = 7
P(10) = 4+5 = 9
P(11) = 5+7 = 12
P(12) = 7+9 = 16 … P(N) = P(N-3)+p(N-2)

풀이 코드 : 9461 파도반 수열

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

long long DP[100];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int T;
    cin>>T;
    for(int t=0;t<T;t++){
        int N;
        cin>>N;

        DP[0] = 1;
        DP[1] = 1;
        DP[2] = 1;

        for(int i=3;i<N;i++){
            DP[i] = DP[i-3] + DP[i-2];
        }

        cout<<DP[N-1]<<"\n";
        memset(DP, 0, sizeof(DP));
    }
}

채점결과