[C++] BOJ(백준) 14719 빗물

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

14719번: 빗물

 

구현 문제다.

블록이 높이 쌓인 곳을 찾는 게 우선이라고 생각했다.

 

1. 처음 생각한 방법은 첫 줄을 기준으로 잡고 기준 보다 더 큰 지점을 찾아가는 것이었다.

큰 지점을 찾기까지 기준의 높이와 해당 줄의 높이 차를 합산하는 방법을 생각했다.

그러나 끝 줄이 항상 높지 않고 그러면 전 기준까지의 합산을 되돌려야 하기 때문에 비효율적이라 생각했다.

이 방법을 패스하고 다른 방법을 생각했으나 글을 쓰는 도중 될 것 같다는 생각이 들어서 코드를 짜보고 성공했다...

(코드 자체는 비효율적인 느낌이 있어서 아래에 별도로 정리하겠다)

 

2. 배열을 순회하면서 앞 뒤 줄의 증가, 감소인 줄을 찾으려 했다. 즉, 주변으로 부터 꼭대기(?)인 줄을 찾았다.

예를 들어 3 0 1 4 2 에서 4를 보면 1에 비해 증가, 2에 비해 감소한다.

여기에 양 끝 줄을 배열에 인덱스와 함께 저장하면 좋을 것 같다고 생각했다.

이 방법도 가능은 할 것 같은데 코드적으로 자잘하고 복잡해질 것 같아서 다른 방법을 생각해 봤다.

 

3. 차례대로 배열을 순회하되, 왼쪽, 오른쪽 각각의 최댓값을 찾는 방법을 택했다.

최댓값을 찾을 때는 해당 줄을 포함해 음수가 나옴을 방지했다.

양쪽의 최댓값 중 작은 값과 해당 줄의 높이의 차를 합산하는 방식으로 진행했다.

줄 개수만큼 반복이 이루어지기 때문에 시간적으로는 비효율적일 순 있지만

코드적으로는 간단할 것 같아서 이 방법을 선택했다.

 

#include <iostream>
using namespace std;

int arr[501];
int main() {
	int n;		cin >> n >> n;
	for (int i = 0; i < n; i++) cin >> arr[i];

	int sum = 0;

	// 양 끝 줄을 제외한 줄 순회
	for (int i = 1; i < n - 1; i++) {
		int maxl = 0, maxr = 0, max;

		// 해당 줄 기준으로 왼쪽의 높이 최댓값
		for (int j = i; j >= 0; j--)
			if (maxl < arr[j]) maxl = arr[j];

		// 해당 줄 기준으로 오른쪽의 높이 최댓값
		for (int j = i; j < n; j++)
			if (maxr < arr[j]) maxr = arr[j];

		// 양쪽 최댓값 중 작은 값을 선택
		max = maxr < maxl ? maxr : maxl;

		// max값과 해당 줄의 높이 차를 합산
		sum += (max - arr[i]);
	}
	cout << sum;
}

시간적으로 비효율적일 것이라고 생각했지만 C++ 자체가 빠르다 보니 0ms였다.

 

// 앞서 설명한 1번에 대한 코드

#include <iostream>
using namespace std;

int arr[501];
int main() {
	int n;		cin >> n >> n;
	for (int i = 0; i < n; i++)cin >> arr[i];

	int sum = 0;	// 최종 합
	int point = arr[0];		// 기준 점
	int index = 0;	// 기준 점의 인덱스

	/*
	기준 점보다 높은 줄이 없을 때 취소를 하긴 어려우므로 임시 합을 저장하는 변수
	높은 줄을 찾기 못하면 semi는 sum에 더하지 않음

	check는 semi를 구하고 sum에 더했는지,
	즉, 마지막 줄까지 계산이 되었는지 확인하는 변수
	*/
	int semi = 0;
	int check = 0;

	for (int i = 1; i < n; i++) {
		// 기준 점보다 높거나 같은 줄을 찾으면
		if (point <= arr[i]) {
			// 기준 점과 인덱스를 바꾸고 semi 계산
			point = arr[i];
			index = i;
			sum += semi;
			semi = 0;
			check = 1;
		}
		else {
			semi += (point - arr[i]);
			check = 0;
		}
	}

	/*
	가장 높은 줄이 마지막이 아니어서 계산이 덜 된 경우
	뒤에서부터 같은 방법으로 진행
	*/
	if (!check) {
		// semi 초기화, 기준 점 재설정
		semi = 0;
		point = arr[n - 1];
		for (int i = n - 1; i >= index; i--) {
			if (point <= arr[i]) {
				point = arr[i];
				sum += semi;
				semi = 0;
			}
			else semi += (point - arr[i]);
		}
	}
	cout << sum;
}