greentea31's Note

https://www.acmicpc.net/problem/2304

풀이 과정

지붕의 수평 부분이 어떤 기둥의 윗면, 지붕의 수직 부분이 어떤 기둥의 옆면과 닿아야 하고, 지붕에 오목한 부분이 있으면 안될 때 창고 다각형의 최소 값을 구하는 문제이다.

지붕의 높이가 높았다가, 낮았다가, 다시 높아지는 경우에 지붕에 오목한 부분이 생기게 된다. 막대의 높이가 가장 높은 곳을 T라 했을 때, 지붕의 시작점부터 T까지는 지붕의 높이가 높아지기만 해야 하고, T부터 지붕의 끝까지는 지붕의 높이가 낮아지기만 해야 한다. 그렇지 않으면 오목한 부분이 생기게 될 것이다.

막대의 길이를 쭉 입력 받고, 막대의 높이가 가장 높은 곳 T를 기준으로 반씩 나눠서, 지붕의 시작부터 T까지는 지붕의 높이가 점점 높아지게, T부터 지붕의 끝 까지는 지붕의 높이가 점점 낮아지게끔 막대를 보고 지붕의 높이를 설정해주면 지붕에 오목한 부분이 생기지 않게끔 창고 다각형의 최소 값을 구할 수 있다.

소스 코드

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

public class Main { // 메모리 11980kb / 시간 84ms
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        // 가장 큰 막대를 기준으로 절반 나눠서 진행할 것이므로 가장 높은 막대의 위치, 막대가 처음 나오는 위치, 막대가 마지막으로
        // 나오는 위치를 저장할 변수들을 선언하였다
        int maxHeight = Integer.MIN_VALUE;
        int maxSpace = Integer.MIN_VALUE;
        int finalSpace = Integer.MIN_VALUE;
        int startSpace = Integer.MAX_VALUE;

        int[] board = new int[1001]; // 4kb정도?  L이 1000이하까지 들어오므로 인덱스 편하게 쓰려고 1001까지 잡았다

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int L = Integer.parseInt(st.nextToken());
            int H = Integer.parseInt(st.nextToken());
            board[L] = H; // 보드에 저장

            if (maxHeight < H) { // 가장 높은 막대의 높이와 위치를 저장한다
                maxHeight = H;
                maxSpace = L;
            }

            startSpace = Math.min(L, startSpace); // 막대가 시작되는 위치를 구한다
            finalSpace = Math.max(L, finalSpace); // 막대가 끝나는 위치를 구한다
        }

        int maxTemp = Integer.MIN_VALUE;
        
        // 일단 가장 긴 막대 길이를 더한다
        int answer = maxHeight;

        // 시작지점부터 높은 막대 위치 직전까지 점검하면서 점검한 막대 길이중 가장 긴 길이를 더해 나간다
        for (int i = startSpace; i < maxSpace; i++) {
            maxTemp = Math.max(board[i], maxTemp);
            answer += maxTemp;
        }

        maxTemp = Integer.MIN_VALUE;
        
        // 끝 지점부터 높은 막대 위치 직후까지 점검하면서 점검한 막대 길이중 가장 긴 길이를 더해 나간다
        for (int i = finalSpace; i > maxSpace; i--) {
            maxTemp = Math.max(board[i], maxTemp);
            answer += maxTemp;
        }

        System.out.println(answer);
    } // end of main
}// end of class

import sys
input = sys.stdin.readline

# 메모리 31256kb / 시간 44ms

N = int(input())
board = [0 for _ in range(1001)]
maxSpace = 0
maxHeight = 0
startSpace = 1001
finalSpace = -1

for i in range(N):
    L, H = map(int, input().split())
    board[L] = H
    startSpace = min(startSpace, L)
    finalSpace = max(finalSpace, L)

    if maxHeight < H:
        maxHeight = H
        maxSpace = L

answer = maxHeight
max_temp = 0

for i in range(startSpace, maxSpace):
    max_temp = max(max_temp, board[i])
    answer += max_temp

max_temp = 0

for i in range(finalSpace, maxSpace, -1):
    max_temp = max(max_temp, board[i])
    answer += max_temp

print(answer)