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

출처: https://www.acmicpc.net/problem/12015

 Input 

6

10 20 10 30 20 50

 

 Output 

4

[BOJ] 11053 가장 긴 증가하는 부분 수열 제의 경우는 N이 최대 1000이기 때문에 DP로 해결가능하였지만

N의 최대 크기가 증가하였기에 구간의 최대값을 가지는 세그먼트 트리 이용

 

DP에서는 i 번째 숫자가 입력될 때,

0 ~ i-1번째 숫자 중에서 자기보다 작은 j번째 숫자를 찾아 DP[j]의 최대값을 구하는 것이었습니다. 

세그먼트 트리에서는 i 번째 숫자 입력될 때, DP[j]의 최대값을 for문으로 탐색하지 않고

 구간의 최대값 세그먼트 트리를 이용하는 것입니다.

즉, tree[]의 단말 노드에는 i번째가 숫자가 입력되었을 때, 0 ~ i-1까지 최대값 + 1이 저장됩니다.

 

시뮬레이션

N = 6일 때, 적혀진 숫자 = [2, 7, 4, 3, 8]

▶ tree[] =   ← 단말노드만 표시

① 숫자 『2』가 들어왔을 때, 구간 [0, 2-1]의 최대값 = 0 → maxVal = 0 + 1 = 1

    ▶ tree[] =   ← 단말노드만 표시

 

② 숫자 『7』가 들어왔을 때, 구간 [0, 7-1]의 최대값 = 1 → maxVal = 1 + 1 = 2

    ▶ tree[] =   ← 단말노드만 표시

 

③ 숫자 『4』가 들어왔을 때, 구간 [0, 4-1]의 최대값 = 1 → maxVal = 0 + 1 = 2

    ▶ tree[] =   ← 단말노드만 표시

    이때, 앞서 들어온 숫자 『7』 의 구간 [0, 7-1] 의 최대값을 다시 구하지 않습니다.

    왜냐하면 최장 증가 수열은 연속되어 입력된 숫자에서 증가되는 부분이기 때문에

    숫자가 들어온 시점에서 [1, 숫자-1]의 최대값을 구하기 때문입니다.

    만약에 이 다음에 숫자 『7』이 다시 입력되었다면 그 때는 숫자 『4』도 포함되어 계산됩니다.

 

④ 숫자 『3』가 들어왔을 때, 구간 [0, 3-1]의 최대값 = 0 → maxVal = 1 + 1 = 2

    ▶ tree[] =   ← 단말노드만 표시

 

⑤ 숫자 『8』가 들어왔을 때, 구간 [0, 8-1]의 최대값 = 0 → maxVal = 2 + 1 = 3

    ▶ tree[] =   ← 단말노드만 표시

    (가장 긴 증가하는 부분 수열은 maxVal 중 최대값)

---

#include <stdio.h>
const int MAX_N = 1e6;
const int MAX_NUM = 1e6;
const int MAX_TREE_SIZE = MAX_NUM * 4;
inline int max(int a, int b) { return (a > b) ? a : b; }
int N, arr[MAX_N + 10];
// 구간 최대값을 가지는 Segment Tree
int tree[MAX_TREE_SIZE];
void initTree(int n, int s, int e) {
    tree[n] = 0;
    if (s == e) { // leaf node
        return;
    }
    int L = n * 2, R = L + 1, m = (s + e) / 2;
    initTree(L, s, m);
    initTree(R, m + 1, e);
}

int query(int n, int s, int e, int qs, int qe) {
    // 범위를 벗어나는 경우
    if ((qe < s) || (e < qs))
        return 0;
    // Query 구간이 [s, e]를 포함하는 경우
    if ((qs <= s) && (e <= qe)) return
        tree[n];
    int L = n * 2, R = L + 1, m = (s + e) / 2;
    return max(query(L, s, m, qs, qe), query(R, m + 1, e, qs, qe));
}

void update(int n, int s, int e, int idx, int v) {
    if (s == e) { // leaf node
        tree[n] = v;
        return;
    }
    int L = n * 2, R = L + 1, m = (s + e) / 2;
    if (idx > m) update(R, m + 1, e, idx, v);
    else update(L, s, m, idx, v);
    // 최대값으로 노드 갱신
    tree[n] = max(tree[L], tree[R]);
}

void input() {
    scanf("%d", &N);
    for (int i = 1; i <= N; i++) {
        scanf("%d", &arr[i]);
    }
}

int solve() {
    int ans = 0, maxVal;
    initTree(1, 1, MAX_NUM);
    for (int i = 1; i <= N; i++) {
        // (현재 값 기준) 앞 구간 최대값 + 1
        maxVal = query(1, 1, MAX_NUM, 1, arr[i] - 1) + 1;
        // 해당 단말 노드의 값을 변경하고 그에 따라 세그먼트 트리값도 변경
        update(1, 1, MAX_NUM, arr[i], maxVal);
        ans = max(ans, maxVal);
    }
    return ans;
}

int main() {
    input();
    printf("%d\n", solve());
}