이번 문제는 백준의 골드 5 빗물 문제이다.
문제를 보았을 때 직관적으로 풀이가 생각나진 않는다.
문제를 한 번 차근차근 읽어보도록 하자.
가로 최대 500 세로 최대 500까지의 공간이 입력으로 주어지고,
공간에서 각 위치별로 기둥이 세워지는데 그 높이가 주어진다.
이 때 빗물이 고이는 총 넓이를 계산해달라고 요구하고 있다.
우선 간단한 것 부터 생각해보면, 고인 빗물의 총량은 높이의 합과 같다.
그 말은, 고인 빗물들의 높이를 모두 더하면 총량이 될 것이라는 것이다.
굳이 넓이를 따로 계산하거나 하지 않아도 된다는 의미가 된다.
그럼 어떤 빗물이 어느 높이까지 고일지 계산하는 것이 관건이다.
구현 문제 - 가장 높은 기둥
따로 뭔가 알고리즘이 떠오르지 않는거 보니 구현 쪽으로 접근해야할 것 같다.
빗물은 보통 양 옆 기둥의 높이가 자신의 높이보다 높게 되면 고이게 된다.
또, 크게 보았을 때 어떤 공간이 높은 기둥에 의해 둘러싸였을 때 고이게 된다.
후자를 어떻게 계산할 것인지가 관건일 것 같다.
- 만약 현재 기둥의 높이를 기준으로 잡고 뒤로 탐색한다면?
- 뒤로 탐색하면서, 낮은 기둥이 나오면 더하고 높은 기둥이 나오면 기준을 바꾼다면?
위의 로직에는 분명한 문제점이 존재한다.
문제에서 주어진 위 그림을 예시로 생각해보자.
5번째 가장 높은 기둥을 지났을 때, 위의 논리대로라면 빗물이 8만큼 고이게 된다.
하지만 그건 전혀 말도 안되는 결과이며, 실제로는 빗물이 1만큼 고여야 한다.
즉, 가장 높은 기둥과 같거나 더 높은 기둥이 나오는 경우에만 성립한다는 것이다.
그러나 높이가 높은 기둥이 기준이 되어야 하는건 가능성이 있어 보인다.
그럼 한 번 반대로 생각해보는건 어떨까?
계속 높은 기둥이 나와야 위의 로직이 성립이 된다고 했으니,
반대로 가장 높은 기둥에서 부터 거꾸로 탐색하며 고이는 빗물을 계산하는 건 어떨까?
가장 높은 기둥을 찾은 뒤, 오른쪽 / 왼쪽을 나누어 탐색하도록 한다면?
이렇게 생각하다 보니, 그 안에서도 계속해서 같은 방식으로 탐색을 해야했다.
자르고 난 왼쪽에서도 또 가장 높은 기둥을 찾고, 오른쪽에서도 찾아야 했다.
이렇게 해서는 빗물량을 계산하기가 쉽지 않을거라고 판단했다.
구현 문제 - 현재 기둥 기준
관점을 바꾸어, 현재 높이를 기준으로 생각해보자.
아까 위에서 빗물은 보통 양 옆 기둥의 높이가 자신의 높이보다 높게 되면 고인다고 했다.
이 말을 해놓고 왜 진작에 이용을 하지 않았을까?
지금 현재 기둥을 기준으로 오른쪽 왼쪽에서 가장 높은 기둥을 찾는다면?
그 둘 중 낮은 쪽 기둥만큼 물이 고이게 될 것이다.
사실 너무나도 간단하게 답을 구할 수 있었던 것이다.
int max_pillow = 0;
for (int i = 0; i < col; i++)
cin >> rain_map[i];
for (int i = 1; i < col - 1; i++) {
int left = 0, right = 0;
for (int j = 0; j < i; j++)
left = max(rain_map[j], left);
for (int j = i; j < col; j++)
right = max(rain_map[j], right);
answer += max(0, min(left, right) - rain_map[i]);
}핵심 로직의 코드는 위와 같이 구현되었다.
현재 기둥으로부터 양 옆을 훑어 각자 가장 높은 기둥을 찾는다.
이후, 둘 중 작은 기둥과 현재 기둥의 높이를 빼어 빗물의 양을 구한다.
역시 이런 창의적인 아이디어를 떠올리는 것이 가장 어렵다.