[백준/BOJ] 12846 무서운 아르바이트 (c++)

[백준/BOJ] 12846 무서운 아르바이트 (c++)

12846번: 무서운 아르바이트

2025.03.10 - [Competitive Programming] - 16. 가장 가까운 작은 값 (Nearest smaller elements, c++)

16. 가장 가까운 작은 값 (Nearest smaller elements, c++)

---

10만개의 일급 정보가 주어져 있을 때 몇일을 연속으로 일했든 가장 작은 일급*일한 날짜로 급여가 지급됩니다.

 

이 때, 최대로 벌 수 있는 금액을 구하는 문제입니다.

 

스택을 이용해 1번 탐색하는 것으로 이 문제를 O(N)에 해결할 수 있습니다.

 

i, j 순으로 급여가 나열되어 있을 때,

 

i > j  인 경우 j일을 넘어가면 기준 급여는 j가 됩니다. 즉, i원으로 돈을 받을 가능성이 없습니다.

 

i < j 인 경우 j를 넘어가더라도 i원으로 돈을 받을 수 있습니다.

 

스택을 이용하면 나중에 들어간 값이 먼저 나오게 됩니다.

 

탐색을 하면서 기준 급여가 될 수 있는 것들은 스택에 남겨 놓습니다.

 

더 이상 기준 급여가될 가능성이 없다면 가능한 기간에 대해서 금액을 계산합니다.

 

단, 구간의 길이를 알아야 하기 때문에 실제 급여가 아닌 index값을 저장해둡니다.

 

스택 앞뒤로는 0을 추가하여 비어있는 스택, 마지막 요소에 대한 처리를 간편하게 할 수 있습니다.

 

만약 현재 급여가 k라면 스택에서 k보다 큰 값들(더 이상 기준 급여가 될 수 없는 값들)을 제거하면서 k 앞까지의 구간에 대해 급여를 계산해봅니다.

 

스택에서 빠져나온 값 s 부터 k 사이의 값은 없었거나, s보다 큰 값이었을 것입니다.

 

그러므로 s~k-1 까지는 s원이 가장 낮은 가격입니다.

 

만약 스택에 k보다 작은 값이 있다면 그 값은 앞으로 또 기준 급여가 될 가능성이 있으니 k를 스택에 추가합니다.

---

#include <bits/stdc++.h>
using namespace std;
#define REP(i, s, e) for (int i=s; i<e; i++)
int N, x;
vector<int> a;

int solve() {
    stack<int> s;
    s.push(0);
    long long ans = 0;
    REP(i, 1, N+2) {
        while(a[s.top()] > a[i]) {
            int z = s.top();
            s.pop();
            long long c = (long long)a[z] * (i-s.top()-1);
            ans = max(ans, c);
        }
        s.push(i);
    }
    cout << ans;
    return 0;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    a.push_back(0);
    REP(i, 0, N) {
        cin >> x;
        a.push_back(x);
    }
    a.push_back(0);
    solve();
    return 0;
}