백준 14727번 [퍼즐 자르기](C++) -yes6686- 티스토리

백준 문제 풀이: 14727 [퍼즐 자르기]

---

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

문제 설명:

주어진 히스토그램에서 가장 큰 직사각형의 넓이를 구하는 문제입니다.

즉, 연속된 높이를 유지하면서 만들 수 있는 가장 넓은 직사각형을 찾는 문제입니다.

---

문제 해결 코드

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

    for (int i = 1; i < n; i++) {
        long long int minHeight, startIdx = i;

        while (!st.empty()) {
            if (st.top().first > arr[i]) { // 현재 막대보다 더 높은 막대 제거
                startIdx = st.top().second;
                minHeight = st.top().first;
                ans = max(ans, minHeight * (i - startIdx)); // 직사각형 넓이 갱신
                st.pop();
            } else {
                break;
            }
        }
        st.push({ arr[i], startIdx });
    }

    // 스택에 남아 있는 요소 처리
    while (!st.empty()) {
        ans = max(ans, (st.top().first * (n - st.top().second)));
        st.pop();
    }

    cout << ans << '\n'; // 최대 직사각형 넓이 출력
}

예제 입력:

7
2 1 4 5 1 3 3

예제 출력:

8

---

코드 설명

• 핵심 알고리즘: 스택을 활용한 히스토그램에서의 최대 직사각형 찾기
• 구현 세부사항:
  • 각 막대를 하나씩 스택에 넣으면서, 현재 높이보다 작은 값이 나오면 직사각형을 계산
  • 스택에서 pop하면서 직사각형 넓이를 갱신
  • 스택이 남아있다면 끝까지 처리하여 최대 값을 찾음
• 시간 복잡도: O(N), 각 요소가 스택에 한 번 삽입되고 한 번 제거됨

---

결과

연속된 구간에서 만들 수 있는 최대 직사각형 넓이를 효율적으로 계산합니다. 스택을 활용한 히스토그램 문제를 연습하기 좋은 문제입니다. 추가적인 질문이나 개선 사항이 있다면 댓글로 알려주세요!