[백준] 9461번

dp에 대해 대충 알게 된듯하다.

그래도 이건 쉬운 문제니까 그러겠지

 

근데 이 문제에서 문제는 long 때문이다.

이 부분은 어떻게 고려해야 하는지 알고 싶다.

#include <iostream>
#include <sstream>
#include <vector>

std::vector<long> wide;

void dp(int);

int main() {
    int t, m = 0;
    std::cin >> t;
    std::vector<int> v(t);
    for (int i = 0; i < t; i++) {
        std::cin >> v[i];
        if (m < v[i]) {
            m = v[i];
        }
    }
    dp(m);
    for (int i=0; i<t; i++) {
        std::cout << wide[v[i]] <<std::endl;
    }
    return 0;
}

void dp(int size) {
    wide.resize(size+1, 0);
    wide[1]=1;
    wide[2]=1;
    for (int i = 3; i <= size; i++) {
        wide[i] = wide[i - 2] + wide[i - 3];
    }
}