[BOJ / C++] 9461 : 파도반 수열

문제 바로가기

9361 : 실버 3

💡 Hmm..

그냥 dp로 규칙 찾아서 풀었는데 틀렸습니다가 떴다. 흠...
그래서 양 끝 값을 넣어줘봤는데 100을 넣으니까 -203220..어쩌구가 나오길래
아 자료형 크기가 넘어가나보다 해서
long long으로 dp배열을 만들어주니까 해결했다!

🖥️ 소스코드

#define fastio ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <string.h>
using namespace std;

/* Method Initialization */
void input();
void solve();

/* Variable Initializati1on */
int n, t, mx = -1e9;
long long dp[102];


int main()
{
    fastio;
    solve();
    return 0;
}


void solve()
{
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 1;
    dp[3] = 1;
    cin >> t;

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

        if (n <= 3){
            cout << 1 << '\n';
            continue;
        }
        else {
            if (dp[n] != 0) {
                cout << dp[n] << '\n';
                continue;
            }
            for (int j = 4; j <= n; j++) {
                dp[j] = dp[j - 2] + dp[j - 3];
            }
            cout << dp[n] << '\n';
        }
    }
}