[알고리즘 문제] 백준9461 - 파도반 수열

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

9461번: 파도반 수열

이 문제는 직접 손으로 그려보면 규칙을 찾을 수 있다.



49 : 28 + 21

37 : 21 + 16

28 : 16+12

...

 

점화식은 dp[i] = d[i-2] + dp[i-3]이다. 다른 풀이를 보면 점화식을 다른 경우도 있는데 상관은 없다. 그리고 처음 dp[]의 값을 모두 구한 다음에 바로 가져다 쓰면 된다.

#include <iostream>

using namespace std;

int main()
{

    int t;
    cin >> t;

    long long dp[101] = {0};

    dp[1] = 1;
    dp[2] = 1;
    dp[3] = 1;

    for (int i = 4; i <= 100; i++)
    {
        dp[i] = dp[i - 2] + dp[i - 3];
    }
    while (t--)
    {
        int n;
        cin >> n;

        cout << dp[n] << "\n";
    }
    return 0;
}