14719번: 빗물
첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치
www.acmicpc.net
저는 2가지 방법으로 해결하였습니다.
하나는 그냥 구현으로, 다른 하나는 세그먼트 트리를 이용하였습니다.
먼저 블록의 최대 높이를 가진 인덱스(idx)를 구합니다.
그리고 왼쪽에서 idx까지, 오른쪽에서 idx까지 순회하면서 현재 최대 높이를 갱신해주고,
만약 현재 최대높이보다 블록의 높이가 더 작으면 그 차이만큼 더해주는 방식입니다.
boj 2304 창고 다각형
www.acmicpc.net/problem/2304 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는
emoney96.tistory.com
세그먼트 트리는 위의 문제와 같은 방식입니다.
트리에 각 높이의 최댓값을 저장합니다.
그 다음 1 ~ N번 블록을 순회하면서 자신을 포함한 왼쪽, 오른쪽 중 최고 높이를 구합니다.
왼쪽 오른쪽 최고 높이 중 낮은 높이만큼 빗물이 쌓이므로 블록높이를 뺀 값을 더해줍니다.
[구현]
|
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
|
#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;
}
|
cs |
[세그먼트 트리]
|
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
57
|
#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;
}
|
cs |
'algorithm > SegmentTree' 카테고리의 다른 글
| boj 12846 무서운 아르바이트 (0) | 2022.08.19 |
|---|---|
| boj 1849 순열 (0) | 2021.09.08 |
| boj 2304 창고 다각형 (0) | 2021.02.25 |
| boj 14438 수열과 쿼리 17 (0) | 2021.02.21 |
| boj 13537 수열과 쿼리 1 (0) | 2021.02.21 |