백준 1989 부분배열 고르기 2

www.acmicpc.net/problem/1989

1989번: 부분배열 고르기 2

이 문제는 앞서 포스팅하였던 부분배열 고르기에서 최대 점수를 받는 실제 부분 배열의 앞 뒤 인덱스까지 출력해야 하는 문제이다. 부분 배열 고르기 문제에서 모노톤 스택을 잘 이해하였다면 최대 점수 갱신 시에 인덱스만 계속 기록해주면 된다.

 

이전 포스팅에서 언급한 바와 같이, 스택의 순기능을 활용하여 O(n^2)의 시간복잡도를 O(n)으로 줄여버렸다. 정확히는 n의 상수 배.

개인적으로 느낀 점은 레이지 세그먼트 트리에서의 '레이지' 개념이 스택에 묻어있다는 것이다. 레이지 세그먼트 트리에서 어떤 구간에 대한 처리를 미뤄두고 나중에 연산을 하는데, 이 문제의 스택 풀이 역시 나중에 연산을 하기 위해 일단 묻어두고 나중에 더블로 가는 연산을 하는 방식이다. 

자세한 설명은 이전 포스팅 참조 부탁드린다. (밑줄 그어진 곳이 링크)

 

<주요 내용>

스택, 실제 부분배열 추적, 모노톤 스택

 

<코드>

최대 점수가 갱신될 때마다, startIdx와 endIdx를 갱신해준다.

#include <iostream>
#include <stack>
#define endl '\n'
using namespace std;
typedef long long ll;

ll s, temp, v;
int n,startIdx=1,endIdx=1,stemp,etemp;
// first: length of a cell, second-first: stacked length, second-second: index
stack<pair<int, pair<ll,int>>> st;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> v;
        temp = 0;
        while (!st.empty() && v < st.top().first)
        {
            temp += st.top().second.first;
            stemp=st.top().second.second;
            if(temp*st.top().first>s){
                startIdx=stemp;
                endIdx=i;
                s=temp*st.top().first;
            }
            st.pop();
        }
        temp += v;
        st.push(make_pair(v,make_pair(temp,temp>v?stemp:i+1)));
    }
    temp = 0;
    etemp=st.top().second.second;
    while (!st.empty())
    {
        temp += st.top().second.first;
        if(temp*st.top().first>s){
            startIdx=st.top().second.second;
            endIdx=etemp;
            s = temp * st.top().first;
        }
        st.pop();
    }
    cout << s << endl;
    cout<<startIdx<<' '<<endIdx<<endl;
    return 0;
}