boj 12846 무서운 아르바이트

https://www.acmicpc.net/problem/12846

12846번: 무서운 아르바이트

일을 연속적으로 해야하며, 한 번만 할 수 있습니다.

또한 일을 한 기간동안 가장 작은 일급 * 기간의 돈을 받습니다.

 

가장 작은 일급이 10이고, 5일동안 일해서 받은 50보다

가장 작은 일급이 20이고, 3일동안 일해서 받은 60이 더 많은 이익을 챙길 수 있습니다.

 

이 문제는 히스토그램 문제와 요구하는 것이 같으며,

https://emoney96.tistory.com/139

boj 6549 히스토그램에서 가장 큰 직사각형

https://emoney96.tistory.com/138

boj 2104 부분배열 고르기

두 문제와 동일한 풀이입니다.

 

트리에는 가장 작은 일급을 가진 인덱스를 저장합니다.

init 함수로 전 구간의 최소 인덱스를 저장합니다.

그리고 partition 함수를 통해 해당 구간에서 가장 작은 값을 가지는 인덱스를 query 함수로 찾은 후 최대 이익을 갱신합니다.

해당 인덱스는 가장 작은 값이므로 제외하고, [s ~ idx - 1] [idx + 1 ~ e] 구간으로 나누어서 같은 과정을 반복합니다.

 

 

#include <iostream>
#include <algorithm>
#define MAX 100001
using namespace std;
typedef long long ll;
 
ll tree[MAX * 4], list[MAX], ans;
int N;
 
void init(int node, int s, int e) {
    if (s == e) {
        tree[node] = s;
        return;
    }
 
    int m = (s + e) / 2;
    init(node * 2, s, m);
    init(node * 2 + 1, m + 1, e);
 
    int l = tree[node * 2];
    int r = tree[node * 2 + 1];
    if (list[l] < list[r]) tree[node] = l;
    else tree[node] = r;
 
    return;
}
 
int query(int node, int s, int e, int l, int r) {
    if (l > e || s > r) return -1;
    if (l <= s && e <= r) return tree[node];
 
    int m = (s + e) / 2;
    int lIdx = query(node * 2, s, m, l, r);
    int rIdx = query(node * 2 + 1, m + 1, e, l, r);
 
    if (lIdx == -1) {
        return rIdx;
    }
    else if (rIdx == -1) {
        return lIdx;
    }
    else {
        return list[lIdx] < list[rIdx] ? lIdx : rIdx;
    }
}
 
void partition(int s, int e) {
    if (s > e) return;
 
    int idx = query(1, 1, N, s, e);
    ans = max(ans, list[idx] * (ll)(e - s + 1));
    partition(s, idx - 1);
    partition(idx + 1, e);
}
 
void func() {
    init(1, 1, N);
    partition(1, N);
 
    cout << ans << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> list[i];
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}