[백준] 9095번

아직 dp가 정확하게 어떤 경우에 사용해야 좋은 알고리즘인지 모르겠다.

확실한건 dp에 대한 정확한 이해가 필요하다는 점이다.

#include <iostream>
#include <vector>

std::vector<int> dp;

void countWay(int n) {
    dp.resize(n + 1, 0);
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        if (i>= 1) {
            dp[i] += dp[i - 1];
        }
        if (i>= 2) {
            dp[i] += dp[i - 2];
        }
        if (i>= 3) {
            dp[i] += dp[i - 3];
        }
    }
}



int main() {
    int t, m = 0;
    std::cin >> t;

    std::vector<int> cases(t);
    for (int i = 0; i < t; i++) {
        std::cin >> cases[i];
        if (cases[i] > m) {
            m = cases[i];
        }
    }

    countWay(m);

    for (int i = 0; i < t; i++) {
        std::cout << dp[cases[i]] << std::endl;
    }

    return 0;
}