백준 1989번 [부분배열 고르기 2](C++) -yes6686- 티스토리

백준 문제 풀이: 1989 [부분배열 문제]

---

문제 링크: https://www.acmicpc.net/problem/1989

문제 설명:

배열에서 연속된 부분 배열을 선택할 때, 선택된 부분 배열의 최소값 × 원소 합의 최댓값을 구하는 문제입니다.

또한, 해당 최대 값을 갖는 부분 배열의 시작 위치와 끝 위치를 출력해야 합니다.

---

문제 해결 코드

#include <iostream>
#include <stack>
using namespace std;

long long int arr[100001]; // 입력 배열
stack<pair<long long int, long long int>> st; // (최소값, 시작 인덱스) 저장

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n; // 배열 크기 입력

    for (int i = 0; i < n; i++) {
        cin >> arr[i]; // 배열 원소 입력
    }

    st.push({ arr[0], 0 });
    long long int maxValue = 0; // 최대 값
    long long int maxX = 1, maxY = 1; // 최대 값을 가지는 구간

    for (int i = 1; i < n; i++) {
        long long int minValue, startIdx = i;
        while (!st.empty()) {
            long long int sum = 0;
            if (st.top().first > arr[i]) {
                startIdx = st.top().second;
                minValue = st.top().first;
                for (int j = st.top().second; j < i; j++) {
                    sum += arr[j]; // 부분 배열의 합 계산
                }
                if (maxValue < sum * minValue) { // 최대값 갱신
                    maxX = st.top().second + 1;
                    maxY = i;
                    maxValue = sum * minValue;
                }
                st.pop();
            } else {
                break;
            }
        }
        st.push({ arr[i], startIdx });
    }

    // 스택에 남아 있는 요소들 처리
    while (!st.empty()) {
        long long int sum = 0;
        for (int i = st.top().second; i < n; i++) {
            sum += arr[i];
        }
        if (maxValue < sum * st.top().first) {
            maxX = st.top().second + 1;
            maxY = n;
            maxValue = sum * st.top().first;
        }
        st.pop();
    }

    cout << maxValue << '\n'; // 최대값 출력
    cout << maxX << " " << maxY << '\n'; // 구간 출력
}

예제 입력:

6
3 1 6 4 5 2

예제 출력:

60
3 5

---

코드 설명

• 핵심 알고리즘: 스택을 활용한 히스토그램 방식으로 부분 배열의 최소값과 합을 계산
• 구현 세부사항:
  • 스택을 이용하여 현재 최소값을 유지하며 배열을 순회
  • 현재 원소보다 작은 값이 나오면, 기존에 쌓인 값들을 꺼내며 부분합을 계산
  • 최대값을 갱신하며 구간의 시작 위치와 끝 위치를 저장
• 시간 복잡도: O(N), 각 요소가 스택에 한 번 삽입되고 한 번 제거됨

---

결과

연속된 부분 배열에서 (최소값 × 원소 합)의 최대값과 해당 구간을 효율적으로 계산합니다. 스택을 활용한 구간 최적화 문제를 연습하기 좋은 문제입니다. 추가적인 질문이나 개선 사항이 있다면 댓글로 알려주세요!