[BOJ/백준][Silver2] 2304 : 창고 다각형 (C++)

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

2304번: 창고 다각형

 

 

 

[난이도] Silver2
[유형] 구현

[풀이]
우선 입력을 받으면서 가장 높은 기둥의 높이 mv를 미리 구해줍니다.
그 뒤, 제일 좌측 부터 확인하면서 지금까지 확인한 기둥 중 가장 높은 기둥의 높이 cur을 유지하면서
cur보다 작은 기둥은 모두 cur로 업데이트해주고, cur보다 큰 기둥이 나타나면 cur을 이 기둥의 높이로 업데이트 해줍니다.
계속 위와 같이 진행하다가 가장 높은 기둥 mv가 나타나면 이 기둥의 index를 l로 저장하고 위 과정을 멈춰줍니다.

우측 방향에서도 위와 동일하게 진행해주고 처음 만난 가장 높은 기둥의 index를 r로 저장해줍니다.

위 과정에서 업데이트한 기둥의 합과 mv*(r-l+1) 를 더해주면 전체 면적이 됩니다.

 

#include <cstdio>
int N,a[1001],ans,l,r,mv;
int main(){
    scanf("%d",&N); 
    for(int i=0;i<N;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        a[u]=v;
        if(v>mv) mv=v;
    }
    int cur=0;
    for(int i=1;i<=1000;i++){
        if(a[i]==mv) {
            l=i;
            break;
        }
        if(a[i]>cur) cur=a[i];
        ans+=cur;
    }
    cur=0;
    for(int i=1000;i>=0;i--){
        if(a[i]==mv) {
            r=i;
            break;
        }
        if(a[i]>cur) cur=a[i];
        ans+=cur;
    }
    printf("%d",ans+mv*(r-l+1));
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver2/2304.cpp