BOJ 11053번 가장 긴 증가하는 부분수열

BOJ : https://www.acmicpc.net/problem/11053

GitHub : https://github.com/junho0956/Algorithm/blob/master/11053/11053/%EC%86%8C%EC%8A%A4.cpp

 

LIS 알고리즘으로 분류되는데

일반적인 동적계획법에 속하는 문제이다.

 

증가하는 부분수열을 찾기 위해서는

dp값을 유지하면서 마지막dp값(가장큰값) 과 현재 값을 비교해가면서 갱신해주면 된다.

 

10, 20, 10, 30, 20, 50 을 기준으로 설명하면

초기 dp : 10

20 과 비교 -> 20이 10보다 크므로 dp 의 마지막+1에 20 삽입 dp : 10 20

10 과 비교 -> 10은 20보다 작으므로 갱신작업을 해준다.

갱신작업이란, 현재 값이 dp 마지막값보다 작다고해서 버리는 값이 아니라

dp 내부의 다른값들과 비교해가면서 다시 수정해 줄 부분이 있는지 확인하는 것이다.

갱신작업을 실시해줘야 좀더 작은 차이로 더 많은 값들을 받을 수 있다.

 

증가하는 부분수열에서는 갱신작업에 의해 수정될 위치는

현재 키값보다 같은 부분은 최대한 뒤, 큰 부분은 최대한 앞 이 되는 부분이다.

 

10 20 에서는 인덱스 0에 수정되므로 변화없이 10 20

30 과 비교 -> 마찬가지로 dp : 10 20 30

20 과 비교 -> 마찬가지로 dp : 10 20 30

50 과 비교 -> 마찬가지로 dp : 10 20 30 50

#include <iostream>
using namespace std;
 
int dp[1001];
int arr[1001];
int N, idx;
 
int bound(int s, int e, int k) {
    int m;
    while (s < e) {
        m = (s + e) / 2;
        if (dp[m] < k) s = m + 1;
        else e = m;
    }
    return e;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin >> N;
 
    for (int i = 0; i < N; i++) cin >> arr[i];
    dp[0] = arr[0];
 
    for (int i = 1; i < N; i++) {
        if (dp[idx] < arr[i]) {
            dp[++idx] = arr[i];
        }
        else {
            int temp = bound(0, idx, arr[i]);
            dp[temp] = arr[i];
        }
    }
 
    cout << idx + 1;
    return 0;
}

 

복습 20.02.09