[백준] 15719번: 빗물
2022. 9. 6. 22:36ㆍTIL💡/Algorithms
https://www.acmicpc.net/problem/14719
진짜 울고 싶다 으헝헝 8ㅅ8
아무리 풀어도 제대로 못 푼다...심지어 이거 골드5인데.. 계속 꼬인다..
문제를 쉽게 풀어내도록 접근했어야 했는데
괜히 이중 for문을 쓰면서 어렵게 풀려고 했다.
최대한 간결하고 쉽게 풀 생각을 우선 해야할 것 같다.
빗물이 쌓이는 구간을 이중 for문으로 구하려 했는데, 이렇게 되면 예외가 많이 생기고 복잡해진다.
대신 한 점씩 각각 for문을 하나씩 쓰면서 왼쪽 벽, 오른쪽 벽을 구해서 각 칸마다 고이는 빗물의 총량을 구하는 게 빠르다.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int h, w, answer = 0;
cin >> h >> w;
vector<int> heights(w);
for(int i = 0;i < w;i++) {
cin >> heights[i];
}
for(int i = 1;i < w;i++) {
int left, right;
left = right = 0;
for(int j = 0;j < i;j++) left = max(left, heights[j]);
for(int j = i + 1;j < w;j++) right = max(right, heights[j]);
int result = min(left, right) - heights[i];
if(result >= 0) answer += result;
}
cout << answer << '\n';
}
'TIL💡 > Algorithms' 카테고리의 다른 글
[백준] 5972번: 택배 배송 (0) | 2022.09.09 |
---|---|
[백준] 2493번: 탑 (0) | 2022.09.07 |
[백준] 16234번: 인구 이동 (0) | 2022.09.06 |
[백준] 17615번: 볼 모으기 (0) | 2022.09.06 |
[백준] 20437번: 문자열 게임2 (0) | 2022.09.06 |