(C++) - 백준(BOJ) 2304번 : 창고 다각형 답

www.acmicpc.net/problem/2304

2304번: 창고 다각형

풀이 및 구현방법을 생각하기 어려웠던 brute force문제였습니다.

 

풀이방법

 빛을 왼편에서 쬐었을 때와 오른편에서 쬐었을 때 빛이 부딪힌 후 그림자와 빛이 비춰지는 모습이 어떻게 구성이 되는가에 대한 생각에서 착안했습니다. 

 1. 1번으로 빛을 쪼였다고 가정해봅시다. 이 때 가장 긴 가운데 (높이가 10짜리) 봉은 갈색 빛이 그 오른편 기둥들의 꼭대기를 비출 수 없도록 하고 있습니다. 

 

 2. 2번으로 빛을 쪼였다고 가정해봅시다. 마찬가지로 가장 긴 기둥에 의해 이 기둥의 왼편 기둥들을 비출 수 없습니다.

 

 3. 그래서 비출 수 없는 부분은 최장봉에 의해서 가려지는 부분이라고 생각했습니다. 가장 긴 기둥이 나왔던 x좌표 다음부터는 가장 긴 기둥의 높이 값을 넣어줍니다.

즉, x좌표를 0부터 1000까지 순회하면서 더 긴 기둥이 나온다면 max값을 갱신해주면서 그 값을 해당 x좌표의 높이로 저장합니다. 반대편도 마찬가지로 저장해줍니다. 이렇게 오른편, 왼편에서 쐈을 때 각자의 빛을 비추는 곳들과 가장 긴 기둥에 의해 생긴 그림자의 높이까지 모두 저장이 되었습니다.

 

 4. 왼편에서 쐇을 때는 가장 긴 기둥의 x좌표를 기준으로 오른쪽에 큰 값들이 저장되어 있으며, 오른편에서 빛을 쐈을 때는 왼편에 큰 값들이 저장되어 있습니다. 다시 x좌표 0~1000까지 순회하며 저장된 각자의 값 중 최솟값이 최소 창고 다각형을 구성하는 한 기둥의 높이가 됩니다. 이를 모두 더해주면 답입니다.

Code

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
int d[1001][3];
int answer,maxVal;
int n,a,b;
int main(){
    cin>>n;
    for(int i = 0; i < n; i++){
        cin >> a >> b;
        d[a][0] = b;
    }
    for(int i = 0; i <= 1000; i++){
        maxVal = max(d[i][0], maxVal);
        d[i][1] = maxVal;
    }
    maxVal = 0;
    for(int i = 1000; i >= 0; i--){
        maxVal = max(d[i][0], maxVal);
        d[i][2] = maxVal;
    }
    for(int i = 0; i <= 1000; i++) answer += min(d[i][1], d[i][2]);
    cout << answer;
}

Test Case

몇 가지 테스트 케이스를 직접 만들어 봤습니다. 도움이 되었으면 좋겠습니다 :0

 

5
1 5
2 4
3 3
4 4
5 5

답 : 25 

5
1 2
2 3
3 2
4 3
5 2

답 : 13

5
1 4
2 5
3 6
4 5
5 4

답 : 24

5
1 5
2 5
3 5
4 5
5 5

답 : 25

5
1 1
2 1
3 1
4 1
5 5

답 : 9

9
2 4
11 4
15 8
4 6
5 3
8 10
13 6
9 10
10 8

답 : 100