백준 9461. 파도반 수열

www.acmicpc.net/problem/9461

9461번: 파도반 수열

 

1	2	3	4	5	6	7	8	9	10
1	1	1	2	2	3	4	5	7	9

패턴을 보면 다섯번째 전의 수를 더해 다음 숫자가 만들어지는걸 볼수 있다.

9 = 7 + 2

d[10] = d[9] + d[9-5]

 

#include <iostream>
using namespace std;

// 숫자 크기 고려해 long long type 
long long d[110];

int main() {
    int t;
    cin >> t;

    while(t--) {
        int n;
        cin >> n;

        d[1] = 1;
        d[2] = 1;
        d[3] = 1;
        d[4] = 2;
        d[5] = 2;
        d[6] = 3;
        d[7] = 4;
        d[8] = 5;
        d[9] = 7;
        d[10] = 9;

        // bottom - up
        for(int i = 11; i <= n; i++) {
            d[i] = d[i-1] + d[i-5];
        }

        cout << d[n] << '\n';
    }
}