티스토리 뷰

오늘의 문제!

https://www.acmicpc.net/problem/1725

입력

첫째 줄에 N이 주어짐

둘째 줄부터 N개 동안 히스토그램의 높이가 주어진다

풀이

라이님의 분할정복에서 분할정복의 이해를 위해 예제로 설명해주신 문제였다
기본적인 풀이법은 여기에서 설명한 것과 비슷하다

1번 mid를 기준으로 왼쪽 중 최대 넓이가 나오는 경우
2번 mid를 기준으로 오른쪽 중 최대 넓이가 나오는 경우
3번 mid를 기준으로 왼쪽과 오른쪽이 겹쳐서 최대 넓이가 나오는 경우

소스

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
#include <stdio.h>
#include <iostream>
using namespace std;
 
int H[100000];
 
int calRectArea(int s, int e){ //넓이 반환
    if(s==e){ // 가로: 1 높이: H[S]
        return H[s];
    }
    int mid = (s+e)/2;
    int area = max(calRectArea(s,mid),calRectArea(mid+1,e));
    
    int h = H[mid], l = mid, r = mid;
    while(l>|| r<e){
        int p = l>s ? H[l-1] : -1//왼쪽으로 확장 높이
        int q = r<e ? H[r+1] : -1//오른쪽으로 확장 높이
        
        if(p>q){ //왼쪽으로 확장
            h = min(h, p);
            l--;
        }
        else//오른쪽으로 확장
            h = min(h,q);
            r++;
        }
        area = max(area, h*(r-l+1));
    }
    return area;
}
 
int main(void){
    int N;
    cin >> N;
    for(int i=0;i<N;i++){
        cin >> H[i];
    }
    cout << calRectArea(0,N-1);
    return 0;
}
 
cs
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2025/02   »
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28
글 보관함