BOJ 27989 - 가장 큰 증가하는 부분 수열 2

문제 링크

• 27989번: 가장 큰 증가하는 부분 수열 2 (acmicpc.net)

27989번: 가장 큰 증가하는 부분 수열 2

 

문제 풀이

$O(N\log N)$

$dp[x]$를 x를 마지막으로 하는 증가하는 부분 수열 의 합중 가장 큰 값이라고 하자.

 

1번째 수부터, 마지막 수까지, 그 숫자와 범위를 마지막으로 하는 부분 수열중 가장 큰 값을 구해보자.

즉, 모든 $i$에 대해, 구간 $[1, i]$ 에서, $A_{i}$로 끝나는 증가수열 중, 가장 큰 합을 $dp[A_{i}]$ 라고 하자.

 

dp테이블이 항상 최적으로 관리되어 있다고 했을 때, 새로운 $dp[i]$를 구하기 위해 전에 구했던 최적해를 이용 할 수 있음을 알 수 있다.

 

식을 세우면, 특정한 $i$에서, $dp[A_{i}] = max_{j < A_{i}} (dp[j] + A_{i}) $ 인 것을 알 수 있다.

 

그럼 특정한 $dp[i]$를 구할 때마다 $O(N)$이 소모 되므로 시간초과가 뜨게 된다.

 

시간초과를 해결 하기 위해, Segment Tree 를 사용해, dp 최적화를 해보자.

 

식이 $dp[A_{i}] = max_{j < A_{i}} (dp[j] + A_{i}) $이므로, 범위 $[0, A_{i})$에 가장 큰 수를 찾는 세그먼트 트리를 만들면 된다.

 

그런데, 될 수 있는 $A_{i}$  값이 $10^{12}$ 이므로, 세그먼트 트리의 크기가 굉장히 커진다.

실제 수는 300000개 밖에 안되고, 세그먼트 트리에서 중요한건 수의 대소관계기 때문에, 좌표압축을 활용하면 된다.

 

#include<bits/stdc++.h>
#define Size(s) (int) s.size()
#define MAX 303030
#define MAX_T MAX*4
 
using namespace std;
 
typedef long long lint;
 
int N;
long long tree[MAX_T], arr[303030];
map<lint, int> compressed;
vector<lint> nums;
 
void update (int node, int s, int e, int idx, lint value) {
    if (s == e) {
        tree[node] = max(tree[node], value);
        return;
    }
 
    int mid = s + e >> 1;
 
    if (idx <= mid) {
        update(node << 1, s, mid, idx, value);
    } else {
        update(node << 1 | 1, mid+1, e, idx, value);
    }
 
    tree[node] = max(tree[node << 1], tree[node << 1 | 1]);
}
 
lint query (int node, int s, int e, int left, int right) {
    if (right < s || e < left) return 0;
 
    if (s <= left && right <= e) return tree[node];
 
    int mid = left + right >> 1;
 
    return max(query(node << 1, s, e, left, mid), query(node << 1 | 1, s, e, mid+1, right));
}
 
 
int main () {
    cin.tie(0);ios_base::sync_with_stdio(0);
 
    cin >> N;
 
    for (int i=0;i<N;i++) {
        cin >> arr[i];
        nums.push_back(arr[i]);
    }
 
    unique(begin(nums), end(nums));
    sort(begin(nums), end(nums));
 
    for (int i=0;i<Size(nums);i++) {
        compressed[nums[i]] = i+1;
    }
 
    for (int i=0;i<N;i++) {
        lint prevMax = query(1, 1, compressed[arr[i]]-1, 1, N);
        update(1, 1, N, compressed[arr[i]], prevMax + arr[i]);
    }
 
    cout << tree[1];
}