boj 2304 창고 다각형

www.acmicpc.net/problem/2304

2304번: 창고 다각형

이 문제와 같은 문제를 코테에서 풀었지만 삽질을 하는바람에 시간없어서 못푼 문제입니다.. ㅠ 문제보자마자 바로 생각이 나더군요...

 

그때 접근했던 풀이방법이 떠올라서 그대로 구현해보니 AC를 받았습니다. 하..

방법은 세그먼트 트리입니다.

우선 위치인 l과 높이인 h를 입력으로 받습니다.

list배열에는 인덱스가 l인 기둥의 높이를 h로 유지합니다.

입력을 받는동안 L에 최대 인덱스를 갱신하고, 트리에 구간 최댓값을 유지합니다.

 

이제 func함수에서 1 ~ L까지 높이를 구합니다.

i번째 기둥의 최종 높이는 1 ~ i의 최댓값과 i ~ L의 최댓값 중 최솟값입니다.

이 값을 list[i]에 다시 넣어줍니다.

출력은 list의 누적합(1 ~ L까지)을 출력해주시면 됩니다.

 

 

 
#include <iostream>
#include <algorithm>
using namespace std;
 
int tree[4004], list[1001];
int N, L, ans;
 
int init(int node, int s, int e) {
    if (s == e) return tree[node] = list[s];
 
    int m = (s + e) / 2;
    return tree[node] = max(init(node * 2, s, m), init(node * 2 + 1, m + 1, e));
}
 
int query(int node, int s, int e, int l, int r) {
    if (l > e || s > r) return 0;
    if (l <= s && e <= r) return tree[node];
 
    int m = (s + e) / 2;
    return max(query(node * 2, s, m, l, r), query(node * 2 + 1, m + 1, e, l, r));
}
 
void func() {
    for (int i = 1; i <= L; i++) {
        int l = query(1, 1, L, 1, i);
        int r = query(1, 1, L, i, L);
 
        list[i] = min(l, r);
 
        ans += list[i];
    }
 
    cout << ans << '\n';
}
 
void input() {
    int l, h;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> l >> h;
        list[l] = h;
        L = max(L, l);
    }
    init(1, 1, L);
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}