창고 다각형( BOJ 2304 )

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

2304번: 창고 다각형

 

문제 파악하기

주어진 막대 기둥을 둘러싸는 가장 작은 창고 다각형의 크기를 구하는 문제입니다. 주어진 입력의 범위가 크지 않기 때문에 어렵지 않게 해결할 수 있는 문제입니다. 이 문제에서 가장 중요한 점은 가장 높은 막대의 위치입니다. 가장 높은 막대의 위치를 기준으로 나눠서 생각해보면 쉽게 해결할 수 있습니다.

 

문제 해결하기

지붕을 오목하게 만들지 않으면서 창고 다각형의 크기를 가장 작게 하기 위해서는 가장 높은 막대를 기준으로 2개의 영역(왼쪽, 오른쪽)으로 나눠서 생각할 수 있습니다. 가장 높은 막대의 왼쪽 부분은 현재 위치를 기준으로 왼쪽에 위치한 막대 중 자신보다 높은 막대에 영향을 받게 됩니다. 반대로, 가장 높은 막대의 오른쪽 부분은 현재 위치를 기준으로 오른쪽에 위치한 막대 중 자신보다 높은 막대에 영향을 받게 됩니다. 즉, 탐색을 양 끝단(0, N-1)에서 시작해서 가장 높은 막대의 위치까지 하나씩 살펴보면서 이전의 값보다 높은 값이 있다면 영역을 더해주면서 전체 창고 다각형의 넓이를 구할 수 있습니다.

 

소스코드

#include <stdio.h>
#include <utility>
#include <vector>
#include <algorithm>
#define PAIR pair<int, int>
using namespace std;
 
int N, l, h;
vector< PAIR > inp;
 
int mi, ret;
 
int abs(int k) { return k>0 ? k:-k; }
 
int sv(int idx, int d) {
    int ret = 0;
    PAIR p;
 
    p = make_pair(idx, 0);
    while(idx != mi) {
        if(p.second < inp[idx].second) {
            ret += abs(inp[idx].first-p.first)*p.second;
            p = inp[idx];
        }
 
        idx += d;
    }
 
    ret += abs(inp[mi].first-p.first)*p.second;
 
    return ret;
}
 
int main() {
    // 입력
    scanf("%d", &N);
    for(int i=0;i<N;i++) {
        scanf("%d %d", &l, &h);
        inp.push_back({l, h});
    }
    
    // 정렬 및 가장 높은 막대 탐색
    sort(inp.begin(), inp.end());
    for(int i=1;i<N;i++) {
        if(inp[mi].second < inp[i].second) mi = i;
    }
    
    // 가장 높은 막대 + 왼쪽 + 오른쪽
    ret = inp[mi].second + sv(0, 1) + sv(N-1, -1);
 
    // 출력
    printf("%d", ret);
}

후기

초등 정올 문제 중 2번에 해당하는 문제라 그리 어렵지 않게 해결할 수 있는 문제입니다. 정렬을 하면 쉽게 해결할 수 있으며, N이 최대 1,000이기 때문에 간단한 정렬 알고리즘을 사용하면 됩니다. 정올 공부를 시작하는 사람에게 추천하고 싶은 문제입니다.