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

https://www.acmicpc.net/problem/2104\

 

[필자 사고]

퀵정렬? 합병정렬? 과 유사한 개념을 이용하여 재귀형태로 문제를 해결해 나갔다.

 

start==end 가 같다면 해당 val*valu 을 return하고 

그렇지 않다면 중심을 기준으로 왼쪽을 갈지 오른쪽을 갈지 결정한 뒤 계속 최대값을 갱신하는 방법이다.

 

이러한 알고리즘은 한번에 습득하기 보다는 계속 문제를 풀어서 재귀적 사고를 키우는게 방법인거 같다.

[코드 해설]

 

• 분할 정복을 이용한 최대 직사각형 구하기 (findMaxRectangle 함수)
  findMaxRectangle 함수는 주어진 범위에서 최대 직사각형의 면적을 구하는 문제를 해결한다.
  • 기본 분할
    주어진 구간 [left, right]을 가운데 mid로 나누어 두 구간 [left, mid]와 [mid+1, right]에 대해 각각 재귀적으로 최대 직사각형의 면적을 계산한다.
  • 중앙 구간 처리
    가운데를 포함하는 최대 직사각형을 계산하기 위해 두 포인터 leftPtr과 rightPtr을 각각 mid와 mid+1로 설정한다.
    이때, 현재 최소 높이를 minHeight로 유지하며, 해당 범위의 직사각형 면적을 계산한다.
    면적은 prefixSum 배열을 이용하여 prefixSum[rightPtr] - prefixSum[leftPtr - 1]로 계산한다.
  • 포인터 이동
    • rightPtr를 확장할 때, values[rightPtr + 1]이 더 크거나 leftPtr이 왼쪽 끝에 도달했을 경우 오른쪽으로 확장한다.
    • 반대로 leftPtr를 확장할 때는 왼쪽으로 이동하며 최소 높이를 업데이트하고 면적을 갱신한다.
• 입력 처리 및 실행
  • main 함수에서 입력값을 받아 배열 values와 누적합 배열 prefixSum을 초기화한다.
  • prefixSum[i]는 values[1]부터 values[i]까지의 합을 저장한다.
  • findMaxRectangle(1, numElements)를 호출하여 전체 범위에서 최대 직사각형 면적을 계산하고 출력한다.

 

 

[소스 코드]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using ll = long long;

int numElements;
ll values[100001], prefixSum[100001];

ll findMaxRectangle(int left, int right) {
	if (left == right) return values[left] * values[left];

	int mid = (left + right) / 2;
	ll maxArea = max(findMaxRectangle(left, mid), findMaxRectangle(mid + 1, right));

	int leftPtr = mid;
	int rightPtr = mid + 1;
	ll minHeight = min(values[leftPtr], values[rightPtr]);
	maxArea = max(maxArea, (prefixSum[rightPtr] - prefixSum[leftPtr - 1]) * minHeight);

    while (left < leftPtr || rightPtr < right) {
        if (rightPtr < right && (leftPtr == left || values[leftPtr - 1] < values[rightPtr + 1])) {
            rightPtr += 1;
            minHeight = min(minHeight, values[rightPtr]);
        }
        else {
            leftPtr -= 1;
            minHeight = min(minHeight, values[leftPtr]);
        }
        maxArea = max(maxArea, (prefixSum[rightPtr] - prefixSum[leftPtr - 1]) * minHeight);
    }
    return maxArea;
}
int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> numElements;
    for (int i = 1; i <= numElements; i++) {
        cin >> values[i];
        prefixSum[i] = prefixSum[i - 1] + values[i];
    }

    cout << findMaxRectangle(1, numElements);

    return 0;
}