[백준 9461번] 파도반 수열 c++

www.acmicpc.net/problem/9461

9461번: 파도반 수열

 

그냥 규칙찾아 풀면 됐던 문제

p(n) = p(n-3)+p(n-2) 하면되고

메모이제이션 배열 초기화하기 뭔가 싫어서

기저사례를 한줄 더 써줌 (n==3)

 

자료형 범위에 주의하자

 

 

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
long dp[101];
 
long  p(int x) {
 
    if (x == 1) return 1;
    if (x == 2) return 1;
    if (x == 3) return 1;
 
    long& ret = dp[x];
    if (ret != 0) return ret;
 
    return ret = p(x - 3) + p(x - 2);
}
int main() {
    int t;
    cin >> t;
    while (t--) {
 
        int n;
        cin >> n;
        cout << p(n) << "\n";
    }
    return 0;
}