백준 창고 다각형 2304

2020-10-26

1. 컴퓨팅적 사고

창고 다각형의 면적이 최소가 되는 값을 찾아내는 문제입니다.

이 문제에서 가장 중요한 점은 좌측과 우측으로 오면서 순차적으로 진행되는 높이보다 값이 같거나 커야합니다. 그래야지 지붕을 만들때 물이 고이지 않도록 만들 수 있게 됩니다.
문제의 조건을 살펴보면 지붕의 수평 부분은 반드시 어떤 기둥의 윗면과 닿아야 한다. 지붕의 수직 부분은 반드시 어떤 기둥의 옆면과 닿아야 한다. 지붕의 가장자리는 땅에 닿아야 한다. 라는 조건을 가지고 있고 지붕의 최대 높이의 인덱스 구하기 지붕의 높이가 가장 높은 인덱스의 값을 구해주어야 합니다.
그 이유는 지붕의 높이가 가장 높은 인덱스의 값을 기준으로 지붕을 만들어야하기 때문입니다. 높이가 10이 되기 때문에 지붕의 최대 높이의 인덱스는 8이 됩니다.

지붕의 높이가 있는 가장 작은 인덱스와 큰 인덱스 구하기 지붕의 높이가 있는 가장 작은 인덱스와 큰 인덱스를 구해주어야 하는이유는 지붕의 최대 높이의 인덱스를 기준으로 좌측, 우측의 최대로 가질 수 있는 지붕의 면적을 구해야하기 때문입니다. 지붕의 높이를 가진 가장 작은 인덱스를 2와 높이 4, 가장 큰 인덱스를 16과 8를 가지게 됩니다.

문제 풀이

map이라는 배열을 하나 선언합니다. 배열의 인덱스값에는 지붕의 인덱스값이 들어가게 되고 값에는 지붕의 높이가 들어가게 됩니다.
예) map[2] = 4, map[16] = 8 값을 입력 받는것과 동시에 지붕의 높이를 가진 인덱스의 최댓값과 최솟값을 Math.max(),Math.min() 함수를 사용하여 구해주게 됩니다.
그리고, 지붕의 최댓값을 가지는 인덱스의값을 구해줍니다. 현재 입력받은 인덱스의 값(지붕의 높이)가 현재 지붕의 높이 보다 클
경우 해당 인덱스 값을 갱신시켜주게 됩니다.

좌측의 경우, 우측의 경우를 나누어서 지붕을 만드는 값을 더해주면서 진행해줍니다.

좌측

지붕의 높이를 가지는 인덱스의 최솟값~지붕의 높이가 가장 큰 지붕의 인덱스값 까지 값을 순회하면서 h의 값을 갱신하면서 순회하는 값의 높이가 더 클 경우에 sum의 값을 더해주게 됩니다.

예를 들면, 높이가 (2,1), (2,3)의 경우를 비교해보겠습니다. 높이가 idx=0 h= 2, idx=1 h= 1일 경우 현재 idx=0의 높이가 idx=1보다 더 크므로, Math.max() 함수를 사용하여 더 큰 h값으로 sum의 값을 더해주면서 진행합니다. 그 이유는 현재 h값이 더 작을 경우 값을 더하게 되면 어떤 기둥의 윗면과 닿거나 옆면에 닿아야한다 라는 조건에 위배되기 때문입니다.

// left -> max_hight_idx
int sum = 0;
int h = 0;
for(int i=min_idx; i<max_hight_idx; i++){
    h = Math.max(h, map[i]);
    sum += h;
}

우측
우측 우측의 경우는 지붕의 높이를 가지는 인덱스의 최댓값~지붕의 높이가 가장 큰 지붕의 인덱스값까지 값을 순회하면서 h의 값 역시 최댓값으로 sum에 값을 더해줍니다. 그 이유는 위와 같습니다. 최종적으로 sum의 값에는 좌측에서의 최대로 가질 수 있는 높이값, 우측에서 최대로 가질 수 있는 높이값을 가지고 있습니다.
하지만, 아직 구해지지않은 값은 max_hight_idx의 값 즉, 가장 높은 지붕의 값을 더해지지않은 상태이기 때문에 map[max_hight_idx]의 값으로 최종 결과값을 출력시켜주게 됩니다.

h = 0;
// right -> max_hight_idx
for(int i=max_idx; i>max_hight_idx; i--){
   h = Math.max(h, map[i]);
   sum += h;
}

응용하는 경우

만약에, 현재 문제를 다른경우로 생각해보면 기존의 지붕의 높이에 기둥을 넣은 부분의 면적을 구하려면 어떻게 구할 수 있을까요? 즉, 채워진 부분의 넓이를 구하는 문제를 구할수도 있습니다. 백준 빗물 14719 문제 과 유사한 문제입니다.

네 맞습니다. 방금까지 우리구한 모든 영역의 넓이에서 - 각 영역의 기존의 값을 빼준다면 채워진 부분의 넓이를 구할 수 있습니다.

int left_sum = 0;
int right_sum = 0;
for(int i=0; i<map.length; i++){
    if(i < max_hight_idx){
        left_sum += map[i];
    }
}

for(int i=map.length-1; i>=0; i--){
    if(i > max_hight_idx){
        right_sum += map[i];
    }
}

이런형식으로 값을 구할 수 있겠습니다.

2. 소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 창고다각형2304 {
    static int[] map;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st;
        map = new int[1001];

        // 인덱스 가장작은값, 큰값 구하고 기둥중에서 높이가 가장 큰 인덱스를 구한다.
        int max_idx = 0;
        int min_idx = 0;
        int max_hight_idx = 0;
        for(int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            map[x] = y;
            max_idx = Math.max(max_idx, x);
            min_idx = Math.min(min_idx, x);

            if(map[x] > map[max_hight_idx]){
                max_hight_idx = x;
            }
        }

        // left -> max_hight_idx
        int sum = 0;
        int h = 0;
        for(int i=min_idx; i<max_hight_idx; i++){
            h = Math.max(h, map[i]);
            sum += h;
        }
        h = 0;
        // right -> max_hight_idx
        for(int i=max_idx; i>max_hight_idx; i--){
            h = Math.max(h, map[i]);
            sum += h;
        }
        int left_sum = 0;
        int right_sum = 0;
        for(int i=0; i<map.length; i++){
            if(i < max_hight_idx){
                left_sum += map[i];
            }
        }
        for(int i=map.length-1; i>=0; i--){
            if(i > max_hight_idx){
                right_sum += map[i];
            }
        }
        System.out.println(map[max_hight_idx] + sum);
        //System.out.println("left painting: "+ left_sum + " right painting : " + right_sum + " max painting :" + map[max_hight_idx]);
    }
}

AlgorithmBOJ

1. 컴퓨팅적 사고

2. 소스코드