[Java] 백준 2304번 : 창고 다각형

문제

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

 

 

접근 방법

1. 왼쪽부터 오른쪽으로 탐색하며 원본 배열과 prefix배열을 비교하며 큰 수를 담아주었고
2. 오른쪽부터 왼쪽으로 탐색하며 원보 배열과 suffix배열을 비교하며 큰 수를 담아주었다.
3. prefix 배열, suffix 배열은 각 방향으로 진행하며 큰 수가 담겨져 있을 것이고 그 수중 작은 것드리 창고의 지붕이 된다.

 

코드

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

public class Main {
    private static StringBuilder sb;
    private static BufferedReader br;
    private static StringTokenizer st;
    private static int N;
    private static int[] arr,prefix,suffix;
    private static int answer;

    //입력
    public static void input() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());

        arr = new int[1010];
        prefix = new int[1010];
        suffix = new int[1010];


        for(int i = 0 ; i < N ; i++){
            st = new StringTokenizer(br.readLine());
            int L = Integer.parseInt(st.nextToken());
            int H = Integer.parseInt(st.nextToken());

            arr[L] = H;
        }
    }

    //실행
    public static void process() {
        for(int i = 1 ; i < prefix.length ; i++){
            prefix[i] = Math.max(prefix[i-1],arr[i]);
        }

        for(int i = suffix.length-2 ; i >= 0 ; i--){
            suffix[i] = Math.max(suffix[i+1],arr[i]);
        }

        for(int i = 1 ; i < arr.length ; i++){
            answer+=Math.min(prefix[i],suffix[i]);
        }
        System.out.println(answer);
    }


    public static void main(String[] args) throws Exception {
        input();
        process();
    }

}