https://www.acmicpc.net/problem/1725
1725번: 히스토그램
첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은
www.acmicpc.net
1. 문제 및 입출력
2. 풀이
Well-Known 문제 답게 풀이가 굉장히 다양합니다. 저는 그중에서도 스택을 이용한 풀이를 소개하려고 해요!
문제의 이해는 쉽습니다.
간단히 가장 큰 넓이의 직사각형을 히스토그램 내에서 찾으면 됩니다.
되게 Naive하게 접근해서 $O(n^2)$으로 알고리즘을 만들 수 있지만 당연히 N이 100000까지이니 불가능하겠죠.
그러니 새로운 풀이를 생각해봅시다.
먼저는 한가지 Lemma를 알아봅시다.
Lemma1
최대 넓이의 직사각형의 높이는 주어진 모든 직사각형의 높이 중 하나에 속한다.
이 문장의 의미는 우리가 최적의 정답을 구했다면 그 높이가 주어진 직사각형들의 높이 중 하나와 같을 것이라는 것입니다.
직관적으로 당연해보이는데요.
증명은 귀류법으로 해봅시다.
증명
아니라고 해봅시다.
우리에게 높이 $h_1 h_2 h_3...h_N$이 주어졌는데 여기서 최대를 구했을 때 그 직사각형의 높이가 $h_1 h_2 h_3...h_N$ 중 어느 것과도 같지 않은 상황입니다.
어떤 K와 W에 대해 K번째부터 W번째까지 직사각형을 택했을 때를 고민해봅시다.
이 때 당연히 이 최대크기의 직사각형의 높이 $h$는 $h_k,h_{k+1}...,h_{W}$들의 최소보다는 작아야합니다. 만약 크면 말이 안되겠죠?
그렇기 때문에 $h \le\min_{k\le i \le w}h_i$입니다. 그런데 우리는 그 중 높이 중 어떤 것과도 같지 않다고 했으므로 $h <min_{k\le i \le w}h_i$입니다.
이는
과 같은 상황입니다.
즉, 이 때 넓이는 $(W-K+1)h$인데
이는 $(W-K+1)h<(W-K+1)min_{k\le i \le w}h_i$ 이고
$(W-K+1)min_{k\le i \le w}h_i$ 도 조건을 만족하므로 모순입니다.
즉,
최대 넓이의 직사각형의 높이는 주어진 모든 직사각형의 높이 중 하나에 속한다.
입니다.
의미
그러므로 이제 우리는 input의 각 높이를 높이로 갖는 직사각형 중 최댓값을 갖는 직사각형들을 비교하면 됩니다!
그런데 문제는 어떻게 비교할 것인가겠죠?
스택을 활용하자.
우리는 스택에 다음과 같은 값들을 저장할 겁니다.
현재 높이보다 높이가 작거나 같은 직사각형의 index 중 최댓값
??? 뭔소린가 싶죠?
아래 그림과 같은 상황을 생각해봅시다.
처음부터 0 1 2 3 4 5 6번 index를 각 직사각형에 붙여주겠습니다.
예를 들어 4번 index의 직사각형 관점에서
현재 높이보다 높이가 작거나 같은 직사각형의 index 중 최댓값은 2입니다.
예를 들어 3번 index 직사각형 관점에서
현재 높이보다 높이가 작거나 같은 직사각형의 index 중 최댓값도 2입니다.
각 직사각형을 index 1번부터 차례대로 본다고 했을 때 스택의 최댓값에는 위의 값들이 저장되게 해줍시다.
만약 잘 성립되게 스택에 넣어준다면
높이를 유지하면서 최대의 넓이를 구할 수 있게 됩니다.
즉 현재 높이를 유지하면서 만들 수 있는 직사각형 중 최대의 넓이를 구하게 될 것입니다.
왜냐면 스택의 Top과 현재 직사각형 사이의 직사각형들의 높이는 현재 직사각형보다 항상 큼이 보장되어 있기 때문입니다.
이런 좋은 성질 때문에 우리는 한번에 가장 큰 직사각형의 넓이를 구할 수 있습니다. index를 저장해놨으니
((현재의 index)-(top의 index))*(현재 높이)로 바로 구할 수 있겠죠~
구현
여기부터는 현재의 의미가 조금 바뀝니다! 주의해서 읽어주세요.
구현 아이디어
- 각 index를 돌면서 높이를 받자.
- 만약 그 높이가 이전의 높이보다 클 경우!
- 스택에 그냥 저장
why? 우리가 위에서 정한 stack의 조건을 만족
바로 직전 index에서의 높이가 작거나 같으면
현재 높이보다 높이가 작거나 같은 직사각형의 index 중 최댓값
- 만약 높이가 작거나 같을 경우!(핵심)
- 스택을 pop
- (pop한 높이) * (pop했을 때의 index)-((pop이 된 상태의 ) stack의 top의 index) 를 계산
- 위를 stack top의 높이가 현재보다 높이나 작거나 같을 때까지 반복
- 현재 높이를 스택에 저장
위와 같은 연산을 진행해주어도 스택의 조건이 유지됩니다!
작거나 같은게 나올 때까지 pop해주므로 강제로 조건을 만족시키고
pop할 때 나오는 높이는 우리가 정한 스택의 조건을 잘 만족하고 있으므로 풀이에 적은 방식으로 넓이를 계산할 수 있습니다.
만약 스택이 비었으면 처음부터 (pop했을 때의 index)까지가 모두 밑변이 됩니다.
- 만약 stack을 다 돌았을 경우?
- 스택 pop
- (pop한 높이) * (맨 끝의 index)-(pop한 index의 차이)
만약 stack을 다 돌았는데 stack에 빈 원소가 남았다는건 각 stack의 원소들 앞의 직사각형들은 모두 자신보다 높이가 높았음을 의미합니다.
그러므로 자신을 높이로 하는 가장 큰 직사각형의 넓이를 구해줍니다.
코드
import sys
from collections import deque
N = int(sys.stdin.readline())
stack = deque()
height = []
ans = -1
for i in range(N):
cur = int(sys.stdin.readline())
height.append(cur)
while stack and height[stack[-1]]>cur:
h = height[stack.pop()]
w = i if not stack else i-stack[-1]-1
ans = max(ans,h*w)
stack.append(i)
while(stack):
idx = stack.pop()
h = height[idx]
w = len(height) if not stack else len(height)-idx
ans = max(ans,h*w)
print(ans)느낀 점
플레 5 쉽지 않네요
~
이 문제가 제게 하나 Breakthrough가 되어 스택 문제들을 잘 풀게 만들어줬던 것 같습니다.
정말 좋은 문제가 많이 생각해볼 법하니 꼭 찬찬히 생각해보시면서 풀길 바랍니다 :)
'Baekjoon' 카테고리의 다른 글
| 백준 21909 Divisible by 3(Python) (2) | 2023.10.02 |
|---|---|
| 7578번 공장(Fenwick tree, python) (0) | 2023.07.08 |
| 1520번 내리막길(dps+dp) (0) | 2023.06.04 |
| 25823번 조합의 합의 합 (0) | 2023.06.01 |
| 17298번 오큰수(DP,Backtracking) Python (1) | 2023.05.31 |
