[알고리즘 풀이 분석] BOJ 2304 창고 다각형

오늘 풀어본 문제는 BOJ 2304 창고 다각형 문제이다!
역시나 작년 NHN 기출과 유사한 문제를 풀어보았고 예전에 풀어봤던 빗물 문제 와 매우 유사한 형태였다.

BOJ 2304 창고 다각형

N 개의 막대 기둥이 일렬로 세워져 있다. 기둥들의 폭은 모두 1 m이며 높이는 다를 수 있다. 이 기둥들을 이용하여 양철로 된 창고를 제작하려고 한다. 창고에는 모든 기둥이 들어간다. 이 창고의 지붕을 다음과 같이 만든다.

1. 지붕은 수평 부분과 수직 부분으로 구성되며, 모두 연결되어야 한다.
2. 지붕의 수평 부분은 반드시 어떤 기둥의 윗면과 닿아야 한다.
3. 지붕의 수직 부분은 반드시 어떤 기둥의 옆면과 닿아야 한다.
4. 지붕의 가장자리는 땅에 닿아야 한다.
5. 비가 올 때 물이 고이지 않도록 지붕의 어떤 부분도 오목하게 들어간 부분이 없어야 한다.

그림 1은 창고를 옆에서 본 모습을 그린 것이다. 이 그림에서 굵은 선으로 표시된 부분이 지붕에 해당되고, 지붕과 땅으로 둘러싸인 다각형이 창고를 옆에서 본 모습이다. 이 다각형을 창고 다각형이라고 하자.

창고 주인은 창고 다각형의 면적이 가장 작은 창고를 만들기를 원한다. 그림 1에서 창고 다각형의 면적은 98 ㎡이고, 이 경우가 가장 작은 창고 다각형이다.

기둥들의 위치와 높이가 주어질 때, 가장 작은 창고 다각형의 면적을 구하는 프로그램을 작성하시오.

입출력

[입력]
첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 빈 칸을 사이에 두고 주어진다. L과 H는 둘 다 1 이상 1,000 이하이다.

[출력]
첫 줄에 창고 다각형의 면적을 나타내는 정수를 출력한다.

나의 풀이

입력 범위가 최대 1000 까지 였기 때문에 단순하고 빠르게 풀면 되는 문제였다.

입력되는 기둥을 그림처럼 2차원 배열에 입력하고 맨 아랫줄 부터 레이저를 쏘듯이 가장 처음 기둥이 나오는 지점 start와 가장 나중에 나오는 기둥 지점 end 를 구해 end-start+1 값을 더해가면 된다.

조금이나마 계산 횟수를 줄이기 위해 기둥중 가장 긴 높이와 가장 처음에 나오는 기둥의 위치, 가장 나중에 나오는 기둥의 위치를 입력받으면서 저장해 두고 그 범위 내에서만 탐색을 진행하였다.

내일 코테에서 나오면 좋겠다.. ^^

코드

#include <iostream>
#include <vector>

// boj 2304 창고 다각형, 구현, 실버 2
using namespace std;

vector<vector<int>> map(1001, vector<int>(1001, 0));

int getArea(int highest, int first, int last){
    int area = 0;

    for (int i = 0; i < highest; ++i) {
        int start = -1, end = -1;
        for (int j = first; j <= last; ++j) {
            if (map[i][j]==1 ){
                if (start == -1){
                    start = j;
                    end = j;
                }else{
                    end = j;
                }
            }
        }
        area += end-start+1;
    }

    return area;
}

int main() {
    ios::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin>>N;

    int highest = -1, first = 1001, last = -1;
    for (int i = 0; i < N; ++i) {
        int L, H;
        cin>>L>>H;

        if (highest < H) highest = H;
        if (first > L) first = L;
        if (last < L) last = L;

        for (int j = 0; j < H; ++j) {
            map[j][L] = 1;
        }
    }

    cout<<getArea(highest, first, last);

    return 0;
}