백준 2304 창고 다각형

작성일 | In |

Problem : 창고 다각형

유형 : 구현

문제 설명

그림1

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

지붕은 수평 부분과 수직 부분으로 구성되며, 모두 연결되어야 한다. 지붕의 수평 부분은 반드시 어떤 기둥의 윗면과 닿아야 한다. 지붕의 수직 부분은 반드시 어떤 기둥의 옆면과 닿아야 한다. 지붕의 가장자리는 땅에 닿아야 한다. 비가 올 때 물이 고이지 않도록 지붕의 어떤 부분도 오목하게 들어간 부분이 없어야 한다. 그림 1은 창고를 옆에서 본 모습을 그린 것이다. 이 그림에서 굵은 선으로 표시된 부분이 지붕에 해당되고, 지붕과 땅으로 둘러싸인 다각형이 창고를 옆에서 본 모습이다. 이 다각형을 창고 다각형이라고 하자.

그림1 . 기둥과 지붕(굵은 선)의 예

창고 주인은 창고 다각형의 면적이 가장 작은 창고를 만들기를 원한다. 그림 1에서 창고 다각형의 면적은 98 ㎡이고, 이 경우가 가장 작은 창고 다각형이다. ? 기둥들의 위치와 높이가 주어질 때, 가장 작은 창고 다각형의 면적을 구하는 프로그램을 작성하시오.

예제 입력

1
2
3
4
5
6
7
8
7
2 4
11 4
15 8
4 6
5 3
8 10
13 6

예제 출력

1
98

해결 전략

문제 조건에서 비가 올 때 물이 고이지 않도록 지붕의 어떤 부분도 오목하게 들어간 부분이 없어야 한다.
이 가장 중요하다.
즉, 2번 위치에 높이 3의 기둥이 있었고, 4번 위치에 높이 2의 기둥이 있지만,
4번 위치 이후에 더 큰 기둥이 있다면
4번 위치에는 높이 3의 천막이 쳐져야한다 고인물 방지 때문에.

가장 높은 기둥의 위치와 높이를 찾는다.
좌,우측 끝부터(천막이 쳐지는 순간부터) 가장 높은 기둥 전까지, 높이를 계속 갱신하며 천막을 친다.

주의할 점

  • 입력에서 기둥의 위치(인덱스)는 정렬되어 들어오지 않는다.

풀이

기둥의 정보를 입력 받는다.

  • 첫번째 기둥 인덱스, 마지막 기둥 위치를 찾아둔다.
  • 가장 높은 기둥의 위치를 찾는다.

가장 높은 기둥까지 좌측, 우측에서 천막을 쳐오기 시작한다.

  • 가장 높은 기둥은 자기 머리 위만 덮으면 되므로, 자기 높이 만큼 바로 더한다.
  • 좌 우에서 계속 천막의 높이를 최고 높이로 갱신하며 천막을 쳐온다.

코드

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
#define MAX 1001
using namespace std;

int warehouse[MAX];
int n;
int min_idx, max_idx, max_height_idx;

int right_sum() {
    int sum = 0, h = 0;
    for (int i = max_idx; i > max_height_idx; --i) {
        h = max(h, warehouse[i]);
        sum += h;
    }
    return sum;
}

int left_sum() {
    int sum = 0, h = 0;
    for (int i = min_idx; i < max_height_idx; ++i) {
        h = max(h, warehouse[i]);
        sum += h;
    }
    return sum;
}

void solve() {
    int answer = warehouse[max_height_idx];
    cout << answer + left_sum() + right_sum();
}

void input() {
    cin >> n;
    int idx;
    while (n--) {
        cin >> idx;
        cin >> warehouse[idx];

        min_idx = min(min_idx, idx);
        max_idx = max(max_idx, idx);
        if (warehouse[idx] > warehouse[max_height_idx]) {
            max_height_idx = idx;
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen("input.txt", "r", stdin);

    input();
    solve();

    return 0;
}

피드백

지역변수 초기화 조심하기.