백준 9461번: 파도반 수열

문제

문제 바로가기> 백준 9461번: 파도반 수열

풀이

점화식(P(N) = P(N-2)+P(N-3))을 구해서 dp로 풀었다!
(+ N이 커짐에 따라 빠르게 증가해 int 범위를 벗어나므로 long long을 사용해야 한다!)

#include<iostream>
#define MAX 101
using namespace std;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    int T, N;
    long long dp[MAX];
    for(int i=1; i<MAX; i++){ // dynamic programming
        if(i<=3) dp[i] = 1;
        else dp[i] = dp[i-2]+dp[i-3]; // 점화식
    }

    cin >> T;
    while(T--){ // print answer
        cin >> N;
        cout << dp[N] << "\n";
    }
}