[백준 9461번] 파도반 수열

풀이

---

식을 순서대로 쭉써보면 점화식을 얻을 수 있다.

주어진 삼각형 예시를 보면서 작성하면 다음과 같은 식을 얻을 수 있었다.

dp[6] = dp[1] + dp[5];
dp[7] = dp[2] + dp[6];
dp[8] = dp[3] + dp[7];
dp[9] = dp[4] + dp[8];

1번~5번까지는 딱히 규칙을 찾을 수 없지만 이후에는 규칙을 찾을 수 있다.

여기서 n=100을 입력했을 때 값의 범위를 넘어가므로 int형으로는 표시할 수 없음만 조심하면 된다.

소스 코드

---

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