[백준 2304번] 창고 다각형

난이도: 실버 II

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

2304번: 창고 다각형

백준 2304번 문제 창고 다각형

단순 구현 문제입니다.

문제에서 주어진 넓이를 구하려면 다음과 같은 과정을 거치면 됩니다.

1. 가장 높은 기둥의 높이를 미리 구해둔다. 이후 모든 기둥을 좌표 순으로 정렬한다.
2. 좌, 우 양 끝에서 다음과 같은 과정을 거친다.
   1. 시작점의 위치와 높이를 기록한다.
   2. 가장 높은 기둥 방향으로 전진하며, 이전에 기록한 높이보다 더 높은 기둥을 찾은 경우 아래와 같은 과정을 거친다.
   3. 정답에 (이전에 기록한 높이) x (현재 찾은 기둥의 위치 - 이전에 기록한 기둥의 위치) 를 더한다.
3. 가장 높은 기둥(들)이 형성하고 있는 높이를 더한다.

문제어서 주어진 예시의 경우, 가장 높은 기둥은 위치 8, 높이 10인 기둥입니다.

이 기둥을 기준으로 좌, 우로 나눈 후, 좌에서는 4 * (4-2), 6 * (8-4) 두 번의 계산을 거치게 되고,

우에서는 8 * (16-9) 한 번의 계산을 거치게 됩니다.

이후 마지막으로 10 * 1을 더하면 답이 됩니다.

 

다음으로 생각해 볼 경우는 '가장 높은 기둥이 두 개 이상 존재하는 경우' 입니다.

이 경우 가장 높은 기둥 중 가장 좌측에 있는 기둥, 가장 우측에 있는 기둥을 따로 기록해야 합니다.

저는 이를 위해 벡터 하나에 위치, 높이를 기록하고, 입력받은 높이가 기존 벡터의 높이보다 더 큰 경우 해당 벡터를 비우고 입력을 받았습니다.

이후 벡터를 좌표 순으로 정렬하고, 맨 앞과 뒤의 좌표를 사용하였습니다.

이 경우에 대한 반례를 제가 만들었으니, 필요하면 사용해 보시기 바랍니다 (링크).

 

5
13 4
6 5
4 3
11 3
9 5

 

답은 42입니다.

 

채점 결과

문제 접근 방법을 빠르게 파악하고, 구현에 실수만 하지 않으면 쉽게 풀 수 있는 문제였습니다.

저는 처음에는 가장 높은 기둥을 구하기 위해 우선순위 큐를 사용했다가 메모리 초과가 나는 바람에...

두 번째 제출에 정답 판정을 받았네요.