백준 1989 c++ "부분배열 고르기 2" -PlusUltraCode-

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

[필자 사고]

이전 문제인 부분배열 고르기에 leftPtr 과 rightPtr을 넓이가 갱신될때마다 기록해주면 쉽게 해결할 수 있다. 

 

• 분할정복:
  문제를 작은 구간으로 나누고, 각각의 구간에서 최대 값을 계산한 뒤 이를 합쳐 전체 구간의 최대 값을 구한다.
• 효율성:
  각 구간에 대해 최소 높이를 유지하면서 넓이를 계산하기 때문에 최악의 경우에도 O(nlog⁡n)O(n \log n)O(nlogn) 복잡도로 동작한다.

 

[코드 해설]

1. 입력 데이터와 초기화
   먼저 배열에 값들을 저장하고, 누적합 배열을 생성하여 구간 합을 빠르게 계산할 수 있도록 준비한다.
   • values[] 배열에 입력 값을 저장한다.
   • prefixSum[] 배열을 사용해 누적합을 계산한다. 이를 통해 특정 구간의 합을 빠르게 구할 수 있다.
2. 분할정복을 이용한 최대 직사각형 넓이 계산
   함수는 배열의 구간을 왼쪽, 오른쪽, 그리고 중간 영역으로 나누어 최대 직사각형의 넓이를 계산한다.
   • 구간이 하나의 원소만 포함하는 경우, 해당 값의 제곱을 직사각형 넓이로 반환한다.
   • 이때, 현재 구간의 시작과 끝 인덱스를 반환한다.
   B. 왼쪽과 오른쪽 구간의 최대 넓이 계산
   • 중간 지점을 기준으로 배열을 왼쪽 구간과 오른쪽 구간으로 나눈다.
   • 각 구간에서 최대 직사각형의 넓이를 재귀적으로 계산한다.
   • 왼쪽과 오른쪽 구간 중 더 큰 값을 선택하며, 해당 구간의 인덱스 정보를 갱신한다.
   C. 중간 구간의 최대 넓이 계산
   • 중간 지점에서 시작하여 왼쪽과 오른쪽으로 확장하며 직사각형을 만든다.
   • 확장된 구간의 최소 높이를 기준으로 직사각형의 넓이를 계산한다.
   • 구간을 확장할 때는 다음 높이를 비교하여 더 높은 방향으로 포인터를 이동한다.
3. A. 기본 케이스
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();
}