문제 풀이 과정을 공유하고자 한다.
문제 출처

1. 문제설명

• 맵이 주어졌을 때 빗물이 고이는 총량을 구하라
  • 각 칸이 1이 된다.

• 아래 이미지와 같이 맵이 주어지면 파란색 영역의 칸 수를 세면 된다.

  

2. 알고리즘 설계

• 열에 해당하는 부분에서 좌, 우 최대값을 탐색하면 된다.
• 첨부 이미지 예시
  • left : 0번에 해당하는 값 3,
  • right : index 4번에 해당하는 값 4

3. 로직

• 2중 for loop로 구현
  • 1번째부터 탐색하는 for문
  • 0번째부터 해당 index 전까지 최대값 찾기
  • 해당 index의 다음 위치부터 최대값 찾기
• 현재 위치의 고인 빗물의 양
  • 좌/우 중 최소값에서 현재 차지하고 있는 칸을 빼주면 된다.

  for (int i = 1; i < w - 1; i++) {
    int left = 0, right = 0;
  
    for (int j = 0; j < i; j++) // left
    for (int j = w - 1; j > i; j--) // right
  
    answer += max(0, min(left, right) - v[i])
  

4. 전체 코드

#include <iostream>
#include <vector>
using namespace std;

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int h, w;
	cin >> h >> w;

	vector<int> v(w);
	for (int i = 0; i < w; i++)
		cin >> v[i];

	int answer = 0;
	for (int i = 1; i < w - 1; i++) {
		int left = 0, right = 0;

		for (int j = 0; j < i; j++)
			left = max(left, v[j]);
		for (int j = w - 1; j > i; j--)
			right = max(right, v[j]);

		answer += max(0, min(left, right) - v[i]);
	}

	cout << answer;
}

5. 소감

• 예전에 학부 4학년 2학기에 면접을 봤었다.
• 현재 문제와 굉장히 유사한 문제가 출제되었다.
• 그 때 당시에는 정확히 기억나진 않지만, 굉장히 창의적(?)으로 풀이했었다.
  • 20/100점을 맞았다…