백준 14727 c++ "퍼즐 자르기" -PlusUltraCode-

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

 

[필자 사고]

이 문제는 히스토 그램과 유사한 알고리즘을 이용하는 문제이다.

필자는 스택을 일용하였고 현재 인덱스의 높이가 스택의 탑 인덱스의높이보다 작을경우 while문을 시작한다.

현재 인덱스 전의 가로 길이를 구하고 topIdx의 높이를 구하여 넓이를 갱신하는 과정이다.

[코드 해설]

1. 스택 myStack을 사용하여 직사각형의 최대 넓이를 계산
   현재 높이가 이전에 스택에 저장된 높이보다 작아질 때, 스택의 가장 위에 있는 인덱스를 사용하여 직사각형의 넓이를 계산한다.
   이때 스택에 남아 있는 높이는 이전까지의 연속된 높이 중 최소값을 나타낸다.
2. 현재 높이와 비교하여 스택을 처리
   배열 arr의 현재 인덱스에서, 스택의 가장 위에 있는 인덱스가 가리키는 높이와 비교한다.
   현재 높이가 스택의 가장 위 높이보다 작을 경우:
   • 스택에서 가장 위에 있는 인덱스를 꺼내고, 해당 높이를 기준으로 가능한 직사각형의 넓이를 계산한다.
   • 이전 높이를 기준으로 한 최대 넓이를 갱신한다.
3. 스택에 인덱스 저장
   스택은 오름차순 높이를 유지하며, 현재 인덱스를 스택에 삽입한다.
4. 배열 끝까지 처리한 후 남은 스택 처리
   배열의 마지막까지 처리한 이후에도 스택에 남아 있는 인덱스들을 차례대로 꺼내며 넓이를 계산한다.
   • 스택이 비어 있다면 해당 인덱스까지가 넓이 계산 범위가 된다.
   • 스택이 비어 있지 않다면, 스택의 새로운 가장 위 인덱스를 기준으로 넓이를 계산한다.
5. 최대 넓이 출력
   계산된 직사각형 넓이 중 가장 큰 값을 출력한다.

[소스 코드]

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

int N;
stack<long> myStack;
vector<long> arr;

void Game_Start() {
	cin >> N;
	arr.resize(N+1);

	for (int i = 1; i <= N; i++) {
		long num;
		cin >> arr[i];
	}
	long resultArea = -1;
	for (int i = 1; i <= N; i++) {

		while (!myStack.empty() && arr[myStack.top()] > arr[i]) {
			int topIdx = myStack.top();
			myStack.pop();
			int currentIdx = 0;

			if (myStack.empty()) {
				currentIdx = i-1;
			}
			else {
				currentIdx = i - myStack.top() - 1;
			}

			resultArea = max(resultArea, currentIdx * arr[topIdx]);
		}

		myStack.push(i);
	}

	while (!myStack.empty()) {
		int topIdx = myStack.top();
		myStack.pop();
		int currentIdx = 0;

		if (myStack.empty()) {
			currentIdx = N;
		}
		else {
			currentIdx = N - myStack.top();
		}

		resultArea = max(resultArea, currentIdx * arr[topIdx]);
	}
	cout << resultArea;
}

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

	Game_Start();
}