백준 2304 창고 다각형 c++ (투 포인터)

문제 출처 : https://www.acmicpc.net/problem/2304

2304번: 창고 다각형

문제

N 개의 막대 기둥이 일렬로 세워져 있다. 기둥들의 폭은 모두 1 m이며 높이는 다를 수 있다. 이 기둥들을 이용하여 양철로 된 창고를 제작하려고 한다. 창고에는 모든 기둥이 들어간다. 이 창고의 지붕을 다음과 같이 만든다.

1. 지붕은 수평 부분과 수직 부분으로 구성되며, 모두 연결되어야 한다.
2. 지붕의 수평 부분은 반드시 어떤 기둥의 윗면과 닿아야 한다.
3. 지붕의 수직 부분은 반드시 어떤 기둥의 옆면과 닿아야 한다.
4. 지붕의 가장자리는 땅에 닿아야 한다.
5. 비가 올 때 물이 고이지 않도록 지붕의 어떤 부분도 오목하게 들어간 부분이 없어야 한다.

그림 1은 창고를 옆에서 본 모습을 그린 것이다. 이 그림에서 굵은 선으로 표시된 부분이 지붕에 해당되고, 지붕과 땅으로 둘러싸인 다각형이 창고를 옆에서 본 모습이다. 이 다각형을 창고 다각형이라고 하자.

그림1 . 기둥과 지붕(굵은 선)의 예

창고 주인은 창고 다각형의 면적이 가장 작은 창고를 만들기를 원한다. 그림 1에서 창고 다각형의 면적은 98 ㎡이고, 이 경우가 가장 작은 창고 다각형이다.

기둥들의 위치와 높이가 주어질 때, 가장 작은 창고 다각형의 면적을 구하는 프로그램을 작성하시오.

입력

첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 빈 칸을 사이에 두고 주어진다. L과 H는 둘 다 1 이상 1,000 이하이다.

출력

첫 줄에 창고 다각형의 면적을 나타내는 정수를 출력한다.

알고리즘 분류

• 자료 구조
• 브루트포스 알고리즘
• 스택

풀이

2021.10.20 - [알고리즘 문제 풀이/백준] - 백준 14719 빗물 c++ (투 포인터)

위의 문제의 하위 버전이라 할 수 있다.

전체적인 풀이는 비슷하지만, 조건이 조금 더 간단하기에 문제 티어가 더 낮게 잡힌다.

 

투 포인터로 풀었기에, 투 포인터라고 분류했지만,

딱히 어떠한 명확한 알고리즘을 이용하는 문제가 아닌 구현 문제라고 볼 수 있고,

음.. 완전 탐색을 근거하여 풀면 되는데, 스택을 이용한 풀이도 있고, 나처럼 투 포인터와 유사한 풀이로 풀 수 있다.

 

우선 왼쪽 구간을 증가하는 구간이라고 하고, 오른쪽 구간을 왼쪽 구간 외에 나머지 공간이라고 하자.

위의 그림에서 왼쪽 구간은 빨간색, 오른쪽 구간은 빨간색,

그리고 가운데 높이가 10인 기둥을 왼쪽 기둥(left)이라 칭하고, 그래프에서 가장 우측에 있는 기둥을 오른쪽 기둥(right)라 칭하자.(오른쪽 구간에서 가장 오른쪽에 있는 기둥)

구간을 구하는 법은, 왼쪽 기둥을 구하고 그를 기준으로 좌, 우를 나누면 된다.

우선 주어진 그래프의 인덱스 0부터 살펴보자.

왼쪽 기둥(left)은 그래프에서 가장 높은 기둥이 될 것이고 이를 구하기 위해, 초기에는 left를 0으로 설정하고,

오른쪽으로 탐색해가면서, left보다 큰 기둥을 만나면 left를 갱신해 주자.

left의 인덱스는 처음엔 0, 2, 4, 8순으로 될 것이고, 8로 고정이 될 것이다.

이때, left를 구하는 과정에서 새로 만난 기둥의 인덱스와 이전 left의 높이를 이용해 왼쪽 구간의 넓이를 구할 수 있을 것이다!

이후, 오른쪽 구간에 대한 정보는, 그래프에서 가장 마지막에 오는 기둥인 (right)의 인덱스를 알고 있으면 된다.

//그래프에서의 기둥의 위치와 높이는 문제의 입력으로 받았다.

 

이제, 오른쪽 기둥에서 오른쪽 구간에 대해 left까지 왼쪽으로 탐색해 나가면 된다.

아직 검사하지 않은 영역 중 가장 오른쪽에 있는 기둥인 right와, 왼쪽에 있는 기둥의 높이를 비교한다.

여기서 2중 반복문이 필요하며, 인덱스는 1씩 감소하는 것이 아니라 어떠한 조건에 의해 스킵되므로, 사실상 1중 반복문처럼 동작한다.

2중 반복문의 바깥 반복문은 right가 left까지를 조건으로 하고,

안의 반복문은 현재 검사할 right기둥을 기준으로 왼쪽의 기둥에서 right보다 큰 기둥 혹은 작은 기둥이 찾는다.

왼쪽의 기둥이 낮은 경우(기둥이 없는 높이가 0인 경우도 포함) 곧바로 answer에 right의 높이를 추가시키고(넓이를 더해주고) 기준이 되는 right는 냅둔다.

왼쪽의 기둥이 높거나 같은 경우, 이 경우는 answer에 왼쪽 기둥의 높이를 추가시키고, 기준이 되는 right를 왼쪽 기둥으로 바꿔준 뒤, 안쪽 반복문을 break로 탈출한다. 아래의 그림을 보면서 로직을 그려보면 이해가 될 것이다.

 

전체적인 로직을 요약하자면,

1. 가장 높은 기둥을 찾는다.

2. 가장 높은 기둥을 기준으로 왼쪽, 오른쪽 구간을 나눈다. (왼쪽은 증가하는 구간 오른쪽은 나머지 구간)

3. 가장 높은 기둥을 찾는 과정에서 왼쪽 구간의 넓이는 구할 수 있다.

4. 오른쪽 구간의 넓이를 구한다.

//참고로 오른쪽 구간을 구할 때, 가장 오른쪽 기둥의 높이는 미리 더해주고, 왼쪽 기둥의 높이는 오른쪽 구간의 넓이를 구하는 로직에 포함시키면 편하다.

 

코드

#include <iostream>

using namespace std;

//1<=n<=1000
int n;
int answer = 0;
int input[1001];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	int cnt = 0;
	int leftIdx = 0;
	int rightIdx = 0;
	for (int i = 0; i < n; i++) {
		int idx;
		cin >> idx;
		cin >> input[idx];
	}
	int sum = 0;
	int right = 1;
	for (; right <= 1000; right++) {
		if (input[leftIdx] <= input[right]) {
			answer += input[leftIdx] * (right - leftIdx);
			leftIdx = right;
		}
		if (input[right]) cnt++;
		if (n == cnt) break;
	}
	answer += input[right];
	while (right > leftIdx) {
		for (int i = right - 1; i >= leftIdx; i--) {		
			//우측 기둥보다 낮다면
			if (input[i] < input[right]) {
				answer += input[right];
			}
			//우측 기둥보다 높거나 같다면
			else {
				answer += input[i];
				right = i;
				break;
			}
		}
	}
	cout << answer;

	return 0;
}