dp PS #boj 14002

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
둘째 줄에는 가장 긴 증가하는 부분 수열을 출력한다. 그러한 수열이 여러가지인 경우 아무거나 출력한다.

풀이

Bottom Up

점화식 D

정의 : 지금 순회하고 있는 수열 항에서의, LIS길이
관계 : (순회 중 현재 항과) 이전 항들과의 비교 시 더 큰 항이 등장시, LIS길이의 최댓값 + 1로 업데이트

역추적

1. 알고리즘은 하나의 값이 다른 값에 의해 바뀌는 경우가 많다. 따라서 왜 바뀌었는지를 기록하면 원래의 값을 알 수 있다

예시 : V의 정의 = LIS길이가 업데이트되는 경우의 인덱스 값

2. 재귀함수를 이용해 구현한다.

예시 : ? -> ? -> ... a[v[p]] -> a[p]

#include <iostream>
#include <vector>

using namespace std;

#define FASTIO   cin.tie(0);  cout.tie(0); ios_base::sync_with_stdio(0);

vector<int> A, D, V;

void go(int p) {
    if (p == -1) {
        return;
    }
    go(V[p]);
    cout << A[p] << ' ';
}


int main() {
    FASTIO;
    int N; cin >> N;
    A.resize(N);
    D.assign(N, 1);
    V.assign(N, -1);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < i; ++j) {
            if ((D[j] + 1 > D[i] ) && (A[j] < A[i])) {
                D[i] = D[j] + 1;
                V[i] = j;
            }
        }
    }
    int ans = D[0];
    int p = 0;
    for (int i=0; i< N; i++) {
        if (ans < D[i]) {
            ans = D[i];
            p = i;
        }
    }
    cout << ans << '\n';
    go(p);
    cout << '\n';
}