[BOJ / C++] 1, 2, 3 더하기 (다이나믹 프로그래밍)

문제링크: https://www.acmicpc.net/problem/9095

 

1. 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int n;
    cin >> n;

    vector<int> d(11, 0);
    d[1] = 1;
    d[2] = 2;
    d[3] = 4;
    for (int i = 4; i < 11; i++) {
        d[i] = d[i-1] + d[i-2] + d[i-3];
    }

    for (int i = 0; i < n; i++) {
        int idx; 
        cin >> idx;
        cout << d[idx] << '\n';
    }
}

 

 

2. 분석

다이나믹 프로그래밍에서는 점화식을 추출해낼 수 있냐 없냐로 갈린다. 점화식을 빼낼 때는 dp 테이블을 나열하면서 패턴을 파악해보는 것이 좋다. 여기서는 4 = d[1] + 3, d[2] + 2, d[3] + 1 인 것을 알 수 있고 따라서 d[4] = d[1] + d[2] + d[3] 이다. 이를 일반항을 이용해 표현하면 d[i] = d[i-1] + d[i-2] + d[i-3]이 된다.

 

3. 시간복잡도

배열을 한 번만 순회하면서 계산하므로 시간복잡도는 O(n)이고, n = 10 < 10^8 이므로 시간제한 1초 내에 통과 가능하다.