2304번: 창고 다각형
첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의
www.acmicpc.net
이 문제와 같은 문제를 코테에서 풀었지만 삽질을 하는바람에 시간없어서 못푼 문제입니다.. ㅠ 문제보자마자 바로 생각이 나더군요...
그때 접근했던 풀이방법이 떠올라서 그대로 구현해보니 AC를 받았습니다. 하..
방법은 세그먼트 트리입니다.
우선 위치인 l과 높이인 h를 입력으로 받습니다.
list배열에는 인덱스가 l인 기둥의 높이를 h로 유지합니다.
입력을 받는동안 L에 최대 인덱스를 갱신하고, 트리에 구간 최댓값을 유지합니다.
이제 func함수에서 1 ~ L까지 높이를 구합니다.
i번째 기둥의 최종 높이는 1 ~ i의 최댓값과 i ~ L의 최댓값 중 최솟값입니다.
이 값을 list[i]에 다시 넣어줍니다.
출력은 list의 누적합(1 ~ L까지)을 출력해주시면 됩니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
#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;
}
|
cs |
'algorithm > SegmentTree' 카테고리의 다른 글
| boj 1849 순열 (0) | 2021.09.08 |
|---|---|
| boj 14719 빗물 (0) | 2021.03.15 |
| boj 14438 수열과 쿼리 17 (0) | 2021.02.21 |
| boj 13537 수열과 쿼리 1 (0) | 2021.02.21 |
| boj 6549 히스토그램에서 가장 큰 직사각형 (0) | 2021.02.19 |