백준 9461 (C++) 파도반 수열

수의 규칙을 보고 떠오르는 점화식을 적었다.

dp[MAX] 배열에 저장했다. 자료형이 long long이 되어야 함에 유의하자.

 

 

#include <iostream>
using namespace std;
using ll = long long;
const int MAX = 105;
int n,t;
ll dp[MAX];
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    dp[1] = 1; dp[2] = 1; dp[3] = 1;
    for (int i = 4; i <= 102; i++) {
        dp[i] = dp[i-2] + dp[i-3];
    }
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        cout << dp[n] << '\n';
    }
    return 0;
}