[백준] 9461 파도반 수열 c++

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

KEY

• dp[i] = dp[i-3] + dp[i-2]의 점화식을 찾았다면 쉽게 풀 수 있는 문제이다.
• 피보나치 수열의 경우 N이 커짐에 따라 빠르게 증가하므로, 반드시 long long 자료형을 써야 한다.

 

Code

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
#include<string>
using namespace std;
long long arr[101];
int t,n;
int main() {
    arr[0] = 1;
    arr[1] = 1;
    arr[2] = 1;
    for (int i = 3; i <= 100; i++) {
        arr[i] = arr[i - 3] + arr[i - 2];
    }
    cin >> t;
    while (t--) {
        cin >> n;
        cout << arr[n - 1] << endl;
    }
}