[백준/C,C++] 9461번: 파도반 수열

www.acmicpc.net/problem/9461

9461번: 파도반 수열

hackids.tistory.com/19

[백준/C,C++] 1904번: 01타일

1904번: 01타일 문제와 비슷하게 점화식만 찾는다면 쉽게 풀 수 있는 문제입니다. 문제에서 주어진 10개의 해 이후 몇 개의 해를 더 나열해 보면 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28입니다. 새로운 삼각형이 그려질 때 더해지는 작은 삼각형이 직전의 삼각형과 5번째 이전의 삼각형이란 것을 알 수 있습니다. P(6) = P(5) + P(1), P(10) = P(9) + (P4) 와 같죠. 이 점화식을 이용해 그대로 로직을 짜주시면 됩니다.

#include<iostream>

using namespace std;

#define MAX 101

long long DP[MAX];

long long triangle(int n)
{
    DP[1] = 1;
    DP[2] = 1;
    DP[3] = 1;
    DP[4] = 2;
    DP[5] = 2;
    for (int i = 6; i <= n; i++) {
        DP[i] = DP[i - 1] + DP[i - 5];
    }
    return DP[n];
}

int main(void)
{
    int T; cin >> T;
    
    for (int i = 0; i < T; i++) {
        int temp; cin >> temp;
        cout << triangle(temp) << "\n";
    }

    return 0;
}