[백준] 1365번 꼬인 전깃줄

[적용한 알고리즘]

세그먼트 트리, LIS

 

[아이디어]

 

[생각의 흐름 / 절차] 

내용

 

[교훈]

오래전부터 LIS 를 쓰면 풀리겠다고 생각했는데

도저히 N^2 의 DP로는 안풀려 잠깐 포기하고 있었던 문제였는데,

최근에 세그먼트 트리를 이용해서 풀 수 있다고 하여 

블로그를 보고 열심히 구현해봤다.

(http://kks227.blog.me/220791986409)

NlogN 으로 구현 가능한게 세그먼트 트리와 이분탐색이라는데, 

이분탐색을 이용하는 방법도 고민해봐야겠다.

 

<코드>

#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

bool compare (pair<int, int> a, pair<int, int> b){
    if (a.first == b.first){ //첫번째 비교 대상이 같다면
        return a.second > b.second; //두번째 애를 비교해 큰 놈을 뒤로 보내준다.
    }
    else {
        return a.first < b.first;
    } // 오름차순으로 정렬해주세요
}

void update(vector<int> &tree, int node, int start, int end, int index, int delta){
    if (index < start || index > end) return; // 범위 밖에 있는 경우
    tree[node] = max(tree[node], delta);
    if (start != end){ //리프 노드가 아닌 경우
        int mid = (start + end) / 2;
        update(tree, node * 2, start, mid, index, delta);
        update(tree, node * 2 + 1, mid + 1, end, index, delta);
    }
}
// 내가 구하고 싶은 값의 범위 : left ~ right, 현재 체크 하고 있는 노드의 범위 : start ~ end
int getMAX(vector<int> &tree, int node, int start, int end, int left, int right){
    if (left > end || right < start) { // 만약에 포함이 안되어있는 경우
        return -1;
    }
    if (left <= start && end <= right){
        return tree[node];
    }
    int mid = (start + end) / 2;
    return max(getMAX(tree, node * 2, start, mid, left, right), getMAX(tree, node * 2 + 1, mid + 1, end, left, right));
}

int main(){
    int n;
    scanf("%d", &n);
    vector<pair<int, int>> a;
    int tree_height = (int)ceil(log2(n));
    int tree_size = (1 << (tree_height + 1));
    vector<int> tree(tree_size);

    for (int i = 0; i < n; i++){
        int x; scanf("%d", &x);
        a.push_back(make_pair(x, i));
    }

    sort(a.begin(), a.end(), compare);

    for (int i = 0; i < n; i++){
        int idx = a[i].second;
        int temp_max = getMAX(tree, 1, 0, n - 1, 0, idx);
        update(tree, 1, 0, n - 1, idx, temp_max + 1);
    }

    printf("%d\n", n - tree[1]);
    return 0;
}