[백준] 12738번 가장 긴 증가하는 부분 수열 3

[백준] 12015번 가장 긴 증가하는 부분 수열 2

의 코드도 동일하다.

 

[적용한 알고리즘]

세그먼트 트리, LIS

 

[아이디어]

세그먼트 트리!

 

[생각의 흐름 / 절차] 

내용

 

[교훈]

이거 풀려고 연산자 오버로딩을 공부했고,

세그먼트 트리의 원리를 정확히 깨우치려고 노력했음..

 

<코드>

#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", tree[1]);

    return 0;
}