🖊️ 문제

https://www.acmicpc.net/problem/14719

🖊️ 생각

1. 현재 기준 가장 높은 블럭을 변수에 저장

시작 블럭을 변수에 저장해놓고, 그보다 더 높은 블럭이 나타나면 고인 물 계산.
마지막 블럭의 경우 시작블럭과 비교해서 더 작은 블럭 기준으로 고인 물 계산

--> 이렇게 했는데, 날 반겨주는 틀렸습니다

반례들을 찾아보다가 내 풀이의 반례를 발견했다.

이렇게.. 노란색으로 블록이 있을 때는,
시작 블럭이 첫 번째 블럭이 아니라 두 번째 블럭이 된다.
그치만 내 풀이에서는 이렇게 갱신할 수가 없었다.

2. 각 블럭에서 고인 물 계산하기

첫 번째와 마지막 블럭을 제외한 각 블럭에서 현재 고인 물들을 계산하자.

각 블럭에 고인 물은,
본인 블럭 기준 왼쪽에 있는 블럭들 중 가장 큰 블럭과 오른쪽에 있는 블럭들 중 가장 큰 블럭, 두 블럭 중 더 작은 블럭 기준으로 구할 수 있다.

이렇게 하려면? 투포인터

몇 가지 처리만 해주면 가볍게 풀리는 문제였다.
다만,, 반례를 생각하기가 까다롭다는게 아쉬운 문제..

만약 저 반례가 입출력 예시에 있었다면 절대 골드까지 내려오지 않았을 문제.. 뭐 다 그런거겠지~

🖊️ 풀이

#include <iostream>
using namespace std;

int arr[501];

int main()
{
	int h, w;
	cin >> h >> w;

	for (int i = 1; i <= w; i++) {
		cin >> arr[i];
	}

	int left = 0;
	int right = 0;
	int block;
	int result = 0;

	for (int cur = 2; cur < w; cur++) {
		for (int i = 1; i < cur; i++) {
			left = max(left, arr[i]);
		}
		for (int i = cur + 1; i <= w; i++) {
			right = max(right, arr[i]);
		}
		block = min(left, right);
		if (block > arr[cur])
			result += block - arr[cur];
		left = 0;
		right = 0;
	}

	cout << result << endl;
}

🖊️ 고칠점

반례에 대해 좀 더 깊게 생각해봐야 할듯

안된다고 맞왜틀? 거리지말고..
천천히 다양한 히든테케를 상상해봐야할 것 같다.