BOJ 2104번 부분배열 고르기

문제 링크

\(1\le{N}\le{10^5} \)

N 개의 음이 아닌 정수가 주어지고 부분 배열 A[i~j]중에 sum(i~j) * min(i~j) 가 가장 큰 것의 값을

구하는 문제이다. 이 문제를 O(NlgN) 과 O(N) 이렇게 두가지 방법으로 풀어보았다.

우선 첫번째로 O(NlgN) 에 푸는 방법이다.

방법은 이렇다. 일단 잘 생각해보면 구간의 min 값이 정해졌다면 min값이 그 것으로 유지되는 한

가장 많은 수를 더하는 것이 최적이라는 것이다. 그렇기 때문에 어떤 하나의 숫자 A[k] 부터 시작해서

왼쪽, 오른쪽으로 시작한 수 A[k] 보다 더 작은 수가 나오기 전까지 쭉쭉 확장시켜보자.

그럼 min(i~j)값이 A[k] 일 때의 최대 점수이다. 그렇다면 min(i~j) 값은 N개 각각의 정수가 될 수가 있으므로

각각의 N개의 수에 대해 최대로 확장했을 때의 점수들의 최대값을 구하면 답이다.

문제는 어떻게 빠른 시간내에(O(N) 보다 빠르게) 최대로 확장시켰을 때의 왼쪽, 오른쪽 끝을 구할 수 있느냐 이다.

구하기만한다면 min(i~j) 는 시작한 수 A[k] 이고 합은 O(N) 전처리로 구간합을 O(1) 에 구할 수 있기 때문에

왼쪽, 오른쪽 경계만 빠르게 구하면 된다.

세그트리로 이것을 O(NlgN) 에 전처리하여 그때 그때 O(1)에 구할 수가 있다.

우선 왼쪽 경계를 말로 풀어서 얘기해보자면

"k번째 수에서 시작해서 왼쪽으로 쭉 볼 때 가장먼저 나오는 A[k]보다 작은 수의 위치 + 1"

즉, 조금 바꿔서 말해보면 'k보다 작은 인덱스에서 A[k] 보다 작은 가장 큰 인덱스' 라고 할 수가 있다.

그럼 tree의 인덱스는 N개의 수로 이루어진 배열 내의 어떤 수이고, tree의 노드 내의 값은 그 값을 가지는 배열의

인덱스라고 하고 왼쪽부터 하나씩 보면서 쿼리를 날려 A[k] 의 왼쪽경계를 구하고 업데이트를 하는 것을

반복하면 된다. 그리고 오른쪽 경계는 거꾸로 하면된다. 

'k보다 큰 인덱스에서 A[k] 보다 작은 가장 작은 인덱스' 이기 때문에 오른쪽부터 하나씩 보면서

쿼리를 날려 A[k] 의 오른쪽경계를 구하고 업데이트 하는 것을 반복하면 된다.

물론 왼쪽 경계를 구할 땐 가장 큰 인덱스 이므로 구간최소고 오른쪽 경계는 구간최대이므로

거의 같은 코드를 두번 짜지 않기 위해 구간최대 트리를 만들어 놓고 구간최소를 할 땐 부호를

바꿔서 넣는다던지 하면 편하다.

#include <bits/stdc++.h>
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define fastio() ios_base::sync_with_stdio(false),cin.tie(NULL)
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int inf = 0x3c3c3c3c;
const long long infl = 0x3c3c3c3c3c3c3c3c;
 
ll tMax[3000003], tMin[3000003];
ll A[100003];
ll L[100003], R[100003];
ll psum[100003];
int N, size;
void update(int pos, ll val, ll *t){
    for(t[pos += size] = val; pos > 1; pos /= 2){
        t[pos / 2] = max(t[pos], t[pos ^ 1]);
    }
}
ll query(int l, int r, ll *t, int isMax){
    ll ret = isMax ? -1 : -N;
    for(l += size, r += size; l <= r; l /= 2, r /= 2){
        if(l & 1) ret = max(ret, t[l++]);
        if(~r & 1) ret = max(ret, t[r--]);
    }
    return ret;
}
ll ans;
int main() {
    fastio();
    cin >> N;
    for(size = 1; size <= 1000000; size *= 2);
    for(int i = 0 ; i < 2 * size; i++) tMax[i] = -1, tMin[i] = -N;
    for(int i = 0 ; i < N; i++) cin >> A[i];
    for(int i = 0 ; i < N; i++) psum[i + 1] = psum[i] + A[i];
    for(int i = 0 ; i < N; i++){
        L[i] = query(0, A[i] - 1, tMax, 1) + 1;
        update(A[i], i, tMax);
    }
    for(int i = N - 1 ; i >= 0; i--){
        R[i] = -query(0, A[i] - 1, tMin, 0) - 1;
        update(A[i], -i, tMin);
    }
    
    for(int i = 0 ; i < N; i++){
        ans = max(ans, (psum[R[i] + 1] - psum[L[i]]) * A[i]);
    }
    cout << ans;
    return 0;
}

두번째로 O(N) 풀이이다. 잘 생각해보면 문제에서 주어진 수식이 히스토그램에서 가장넓은 직사각형을

구하는 것과 같다는 것을 알 수가 있다. 그렇기 때문에 사실상 이 문제에서 각 막대기의 가로 폭만

1이아닌 임의의 정수라는 점만 다르기 때문에 같은 방법(스위핑)으로 풀면된다.

#include <bits/stdc++.h>
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define fastio() ios_base::sync_with_stdio(false),cin.tie(NULL)
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int inf = 0x3c3c3c3c;
const long long infl = 0x3c3c3c3c3c3c3c3c;
int N;
ll A[100003];
ll psum[100003];
stack<pair<int, int> > stk;
int main() {
    fastio();
    cin >> N;
    A[N + 1] = 0;
    ll ans = 0;
    for(int i = 1; i <= N + 1; i++){
        cin >> A[i];
        psum[i] = psum[i - 1] + A[i];
        while(!stk.empty() && stk.top().first > A[i]){
            auto p = stk.top();
            stk.pop();
            int h = p.first;
            int prv = stk.empty() ? 0 : stk.top().second;
            ans = max(ans, (psum[i - 1] - psum[prv]) * h);
        }
        stk.push({A[i], i});
    }
    cout << ans;
    return 0;
}