[백준 9461] 파도반 수열

0. 제목

• 백준 9461 파도반 수열
• BOJ 9461 파도반 수열
• C++ 9461 파도반 수열

---

1. 문제

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

---

2. 풀이

• 점화식을 찾으면 쉽게 풀리는 문제이다.
• 두가지 점화식으로 풀리는데 다음과 같다.
• dp[i] = dp[i-2] + dp[i-3]
• dp[i] = dp[i-1] + dp[i-5]
• 두가지 중 하나로 코드를 짜면 정답이다.

---

3. 코드

#include <iostream>
using namespace std;
 
int main(int argc, const char * argv[]) {
    int T, N;
    long int dp[101] = {0};
    cin >> T;
    
    dp[1] = 1;
    dp[2] = 1;
    dp[3] = 1;
    for(int j = 4; j <= 100; j++)
        dp[j] = dp[j-2] + dp[j-3];
    
    for(int i = 0; i < T; i++){
        cin >> N;
        cout << dp[N] << '\n';
    }
    
    return 0;
}