[백준 9461] 파도반 수열 (C++)

문제

백준 9461

9461번: 파도반 수열

풀이

점화식만 알면 쉽게 풀 수 있는 문제입니다.

점화식은 직관...으로 찾았습니다.

인덱스가 커지면 배열의 값이 int 범위를 초과하므로 배열을 long long 형으로 선언합니다.

소스 코드

#include<iostream>
using namespace std;
 
long long dp[101];
 
int main()
{
    int t;
    int num;
    dp[1] = 1;
    dp[2] = 1;
    dp[3] = 1;
    dp[4] = 2;
    dp[5] = 2;
    for (int i = 6; i <= 100; i++)
    {
        dp[i] = dp[i - 1] + dp[i - 5];
    }
    cin >> t;
    for (int i = 0; i < t; i++)
    {
        cin >> num;
        cout << dp[num] << '\n';
    }
    return 0;
}