[BOJ / C++] 가장 큰 증가하는 부분 수열 (다이나믹프로그래밍)

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

 

1. 코드

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

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

    int n;
    cin >> n;

    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    vector<int> d(n, 0);
    d[0] = arr[0];
    for (int i = 0; i < n; i++) {
        d[i] = arr[i];
        for (int j = 0; j < i; j++) {
            if (arr[j] < arr[i]) {
                d[i] = max(d[i], d[j]+arr[i]);
            }
        }
    }

    cout << *max_element(d.begin(), d.end());
}

 

 

2. 시간복잡도

dp테이블을 채울 때 각 원소를 마지막으로 하는 가장 큰 증가하는 부분수열을 찾기 위해 0 ~ i-1까지를 순회해야하므로 시간복잡도는 \(O(n^{2})\)이 된다. \(n=10^{3}\)이므로 \(O(n^{2}) = 10^{6} < 10^{8}\)이므로 시간제한 1초 내에 통과 가능하다.

 

 

3. 분석

1. dp테이블:

i번째 원소를 마지막으로 했을 때 가장 큰 증가하는 부분 수열의 합으로 dp테이블을 설정한다.

 

2. 점화식:

d[i] = (index 0 ~ i-1까지 중 가장 큰 d[i]) + arr[i]

 

점화식에서 index 0 ~ i-1까지 중 가장 큰 d[i]를 찾아 내는 것의 구현방법은 다음과 같다.

초기 d[i] = arr[i]로 설정해주고 내부 loop(j)에서 arr[j] < arr[i] 인 d[j] 중에서 d[i] = max(d[i], d[j] + arr[i])로 갱신해주면 된다.