[ BOJ 백준 1725번 - 히스토그램 ] 해설 및 코드

 

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

1725번: 히스토그램

 

목적

왼쪽과 그림과 같은 히스토그램에서 오른쪽 그림과 같은 직사각형 넓이의 최대값을 구한다.

접근법

1. 분할정복 알고리즘으로 접근하자. (백준 2104 - 부분배열 고르기 문제와 같이 스위핑 알고리즘으로 접근할 수도 있다.)

 

#include<iostream>
#include<cmath>
using namespace std;
 
int a[100001];
int maxSize(int start,int end){
    if(start==end)return a[end];
    
    int mid=(start+end)/2;
    int lo=mid,hi=mid+1;
    int height=min(a[lo],a[hi]);
    int ret=height*2,tmp;
    
    while(start<lo||hi<end){
        if(start==lo) tmp=++hi;
        else if(hi==end) tmp=--lo;
        else if(a[lo-1]<a[hi+1]) tmp=++hi;
        else tmp=--lo;
        
        height=min(height,a[tmp]);
        ret=max(ret,height*(hi-lo+1));
    }
    
    return max(ret,max(maxSize(start, mid),maxSize(mid+1,end)));
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;
    for(int i=0;i<n;++i)cin>>a[i];
    cout<<maxSize(0, n-1);
}
 

 

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.