급하게임개발

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

이 문제는 내가 완전 감을 잘못 잡고 풀고 있었다. 이 문제를 증가수열 비슷하게 풀려고 했었다 하지만 이렇게 풀면 로직이 꼬였는데 테스트케이스 몇개는 잘나왔으나 몇개는 매우 잘 나오지 않았다.

이 문제의 로직은 현재 나를 기준으로 내왼쪽에서의 최대높이와 내오른 쪽의 최대높이를 비교해서 낮은 높이를 선택 해주는 문제 였다 단 오른쪽 과 왼쪽의 최대높이가 나보다는 클때만 빗물이 받아지니 해당 상황일때만 계산하도록 코드를 작성한다 그림으로 나타내면 대충 아래와 같다

해당 로직에 대한 코드는 아래 와 같다

#include <iostream>
#include<algorithm>
using namespace std;
int h, w;
int arr[500];
int main() {
	cin >> h >> w;
	int result = 0;
	for (int i = 0; i < w; i++) {
		cin >> arr[i];
	}
	for (int i = 1; i < w - 1; i++) {
		int lmax = 0;
		int rmax = 0;
		for (int j = 0; j < i; j++) {
			if (lmax < arr[j] && arr[j]>arr[i])
				lmax = arr[j];
		}
		for (int j = i + 1; j < w; j++) {
			if (rmax < arr[j] && arr[j]>arr[i])
				rmax = arr[j];
		}
		if (lmax != 0 && rmax != 0)
			result += min(lmax, rmax) - arr[i];
	}
	cout << result;

}