BOJ 11722번 가장 긴 감소하는 부분수열

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

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

 

 

가장 긴 감소하는 부분수열을 이룰려면

현재 키값에 대해

1) 같으면 반환

2) 현재 위치가 키값보다 크면 오른쪽탐색

3) 현재 위치가 키값보다 작으면 왼쪽탐색

위 3가지 방법으로 문제를 해결하면 됩니다.

 

#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;
 
int dp[1000];
int arr[1000];
 
int bound(int s, int e, int key) {
    int mid;
    while (s < e) {
        mid = (s + e) / 2;
        // 감소하는 수열
        // 현재키값보다 작으면 덮는다
        // 현재키값보다 크면 못덮는다
        // 현재키값과 같으면 정지
        // => 현재키값보다 작거나 같은 위치를 찾는다
        if (dp[mid] == key) return mid;
        else if (dp[mid] < key) e = mid;
        else if (dp[mid] > key) s = mid + 1;
    }
 
    return e;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    int N; cin >> N;
    for (int i = 0; i < N; i++) cin >> arr[i];
 
    dp[0] = arr[0];
    int lis = 0;
 
    for (int i = 1; i < N; i++) {
        if (arr[i] < dp[lis]) {
            dp[++lis] = arr[i];
        }
        else {
            // 감소하는 수열
            int lower = bound(0, lis, arr[i]);
            dp[lower] = arr[i];
        }
    }
 
    cout << lis+1;
 
    return 0;
}

 

 

복습 20.02.09