[Week 2] #9461 self review - yujungee

[yujungee]

#9461 self review

• 파일명: algo_2022/#9461.cpp (branch - yujungee)
• 수행시간: 4ms
• 메모리: 2020KB

1. 문제 해결 과정

문제에서 준 수열의 점화식을 뜯어보니 P(N) = P(N-2) + P(N-3) 이 나왔다.
n-2, n-3 이 음수가 되지 않도록 cache[2]까지 미리 수를 대입했다.
처음 cache를 int로 선언했는데 숫자가 커지기 때문에 long long으로 바꾸었다.

2. 아이디어

dp와 메모이제이션을 사용했다.

3. 코드 설명

#include <iostream>
#include <cstring>

using namespace std;
long long cache[101];

long long solve(int num){
    
    if (cache[num] < 0) return cache[num] = solve(num-2)+solve(num-3);
    
    return cache[num];
    
}

int main(){
    int tc;
    cin >> tc;
    
    while(tc--){
        memset(cache, -1, sizeof(cache));
        cache[0] = 0;
        cache[1] = 1;
        cache[2] = 1;
        int n;
        cin >> n;
        cout << solve(n) << endl;
    }
}