백준 9461. 파도반 수열

tose33 2021. 3. 10. 15:52

www.acmicpc.net/problem/9461

9461번: 파도반 수열

오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의

www.acmicpc.net

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';
    }
}