boj 14719 빗물

www.acmicpc.net/problem/14719

14719번: 빗물

저는 2가지 방법으로 해결하였습니다.

 

하나는 그냥 구현으로, 다른 하나는 세그먼트 트리를 이용하였습니다.

 

먼저 블록의 최대 높이를 가진 인덱스(idx)를 구합니다.

그리고 왼쪽에서 idx까지, 오른쪽에서 idx까지 순회하면서 현재 최대 높이를 갱신해주고,

만약 현재 최대높이보다 블록의 높이가 더 작으면 그 차이만큼 더해주는 방식입니다.

 

 

emoney96.tistory.com/154

boj 2304 창고 다각형

세그먼트 트리는 위의 문제와 같은 방식입니다.

 

트리에 각 높이의 최댓값을 저장합니다.

 

그 다음 1 ~ N번 블록을 순회하면서 자신을 포함한 왼쪽, 오른쪽 중 최고 높이를 구합니다.

왼쪽 오른쪽 최고 높이 중 낮은 높이만큼 빗물이 쌓이므로 블록높이를 뺀 값을 더해줍니다.

 

 

[구현]

#include <iostream>
#include <algorithm>
using namespace std;
 
int list[501];
int N, M, maxheight, idx;
 
void func() {
    int ans = 0;
    int nowmax = 0;
    for (int i = 1; i <= idx; i++) {
        nowmax = max(nowmax, list[i]);
 
        if (nowmax > list[i]) {
            ans += (nowmax - list[i]);
        }
    }
 
    nowmax = 0;
    for (int i = N; i > idx; i--) {
        nowmax = max(nowmax, list[i]);
 
        if (nowmax > list[i]) {
            ans += (nowmax - list[i]);
        }
    }
 
    cout << ans << '\n';
}
 
void input() {
    cin >> M >> N;
    for (int i = 1; i <= N; i++) {
        cin >> list[i];
        if (maxheight < list[i]) {
            maxheight = list[i];
            idx = i;
        }
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}

 

 

[세그먼트 트리]

#include <iostream>
#include <algorithm>
using namespace std;
 
int list[501], tree[2001];
int N, M;
 
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() {
    int ans = 0;
    for (int i = 1; i <= N; i++) {
        int l = query(1, 1, N, 1, i);
        int r = query(1, 1, N, i + 1, N);
 
        int result = min(l, r);
 
        if (list[i] < result) {
            ans += result - list[i];
        }
    }
 
    cout << ans << '\n';
}
 
void input() {
    cin >> M >> N;
    for (int i = 1; i <= N; i++) {
        cin >> list[i];
    }
    init(1, 1, N);
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}