BOJ 9461 파도반 수열

boj 9461 파도반 수열

- 문제 링크

https://www.acmicpc.net/problem/9461

- 문제 해설

첫 5항만 제외하고 나머지 항들은 전부 규칙을 따라 증가하는 형태이다.
P(1)부터 P(10)을 보면 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 이다.
길이가 3인 삼각형은 1과 2를 더해서 생기고, 길이가 4인 삼각형은 1과 3을 더해서, 길이가 5인 삼각형은 1과 4를 더해서 생긴다.
D[i] = D[i-1] + D[i-5] 의 규칙을 따라 증가한다.
그러므로 1~5항을 따로 초기화해주고 나머지는 위 점화식을 따라 구해준다.

- 코드 보기

#include <iostream>
using namespace std;

int t;
int n;
long long P[105];

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> t;
    for (int i = 1; i <= 3; i++) P[i] = 1;
    P[4] = 2;
    P[5] = 2;

    for (int i = 1; i <= t; i++)
    {
        cin >> n;

        for (int j = 6; j <= n; j++)
        {
            P[j] = P[j - 1] + P[j - 5];
        }

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