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

백준 문제 풀이: 2104 [부분배열 고르기]

---

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

문제 설명:

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

이 문제는 스택을 활용한 히스토그램 문제와 유사하며, 특정 구간에서의 최소값을 빠르게 찾는 방식으로 해결할 수 있습니다.

---

문제 해결 코드

#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 ans1 = 0;

    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]; // 부분 배열의 합 계산
                }
                ans1 = max(ans1, 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];
        }
        ans1 = max(ans1, sum * st.top().first);
        st.pop();
    }

    cout << ans1 << '\n'; // 최댓값 출력
}

예제 입력:

4
1 2 3 4

예제 출력:

21

---

코드 설명

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

---

결과

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