[백준 알고리즘/BOJ/C++] 9461 파도반 수열

 

 

파도반 수열이라고 인터넷에 치면 점화식이 많이 나오지만 직접 찾아보자

​

1 1 1 2 2 3 4 5 7 9 12 ···

쉽게 점화식 P(n) = P(n-2) + P(n-3)을 정의할 수 있다

 

 

#include <iostream>
using namespace std;
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    long long arr[101] = { 0, 1, 1, 1, };
    for (int i = 3; i <= 100; i++) {
        arr[i] = arr[i - 3] + arr[i - 2];
    }
 
    int t, n;
    cin >> t;
 
    while (t--) {
        cin >> n;
        
        if(n<=3)
            cout << 1 << "\n";
        else
            cout << arr[n] << "\n";
    }
}

 

이 와중에 또 실수함...

이것도 피보나치랑 비스무리한 추이로 수가 커지는데 배열을 int로 선언했었다

배열은 long long!!