[JAVA][백준] 2304 - 창고 다각형

문제

백준 2304(https://www.acmicpc.net/problem/2304)

풀이

왜 이렇게 어렵게 다가오는지 모를 정도로 어려웠다.. ㅋㅋ 머리가 안 돌아간다.

 

 

입력받은 값이 위와 같다면 최댓값을 중심으로 값을 더해주고 최댓값이 한번만 더해지면 되는 형태이다.

 

 

입력받은 값이 위와 같이 최대값이 여러 개인 상황이라면 최댓값의 양 끝 값 사이의 값은 최댓값으로 채워주면 된다.

 

코드

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

/**
 * 백준
 * 창고 다각형
 */
public class No2304 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int[] arr = new int[1001];
        int n = Integer.parseInt(br.readLine());
        int maxHeight = 0;  //최대 높이
        
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int idx = Integer.parseInt(st.nextToken());
            int height = Integer.parseInt(st.nextToken());

            maxHeight = Math.max(height, maxHeight);

            arr[idx] = height;
        }

        int result = 0; //결과
        int[] maxPoint = new int[2];    //높이가 최대값인 곳의 좌표 양 끝을 저장

        int h = 0;
        for (int i = 0; i <= 1000; i++) {
            if(arr[i] == maxHeight){//최대값과 같으면
                maxPoint[0] = i;    //왼쪽좌표(x좌표 최소)  저장
                break;
            }

            if(h < arr[i]){
                h = arr[i];
            }
            result += h;
        }

        h = 0;
        for (int i = 1000; i >= 0; i--) {
            if(arr[i] == maxHeight){//최대값과 같으면
                maxPoint[1] = i;    //오른쪽좌표(x좌표 최대) 저장
                break;
            }

            if(h < arr[i]){
                h = arr[i];
            }
            result += h;
        }

        //양쪽의 좌표를 빼주고 최대 높이 곱을 더해줌
        result += (maxPoint[1] - maxPoint[0] + 1) * maxHeight;

        System.out.println(result);
    }

}

 

중요한 부분은 최대 높이인 값을 어떻게 더해주느냐였던 것 같다.