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

 

www.acmicpc.net/problem/2304

2304번: 창고 다각형

 

오랜만이라서 그런지 절대 쉽지 않았습니다...

 

꽤 오래 걸렸네요.

 

핵심은 기둥이 높아질 때마다 지붕 높이를 갱신하고 넓이를 추가해준다는 점.

그리고 동일한 방법을 정방향, 역방향으로 수행하면서 전체 넓이를 계산하는 겁니다.

 

처음에 한 방향으로만 풀려고하니 복잡도가 확 올라가 버리더군요.

그리고 주의할 점은 정방향으로 쭉 가서 계산하면서 마지막 가장 높은 기둥의 위치를 저장해두고

그 지점까지만 역방향 연산을 수행해야 계산 중복이 일어나지 않습니다.

 

 

 

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("testcase.txt"));
        int N = Integer.parseInt(br.readLine());
        List<Pillar> pillars = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int left = Integer.parseInt(st.nextToken());
            int right = left+1;
            int height = Integer.parseInt(st.nextToken());
            pillars.add(new Pillar(left, right, height));
        }

        pillars.sort(Comparator.comparingInt(p -> p.left));

        int area = 0;
        int tallestPillarIndex = 0;
        Pillar roofPillar = pillars.get(0);
        //왼쪽에서 오른쪽으로
        for (int i = 1; i < pillars.size(); i++) {
            Pillar current = pillars.get(i);
            if(roofPillar.height <= current.height) {
                int width = current.left - roofPillar.left;
                area += width * roofPillar.height;

                roofPillar = current;
                tallestPillarIndex = i;
            }
        }

        //중간 점검
//        System.out.println(area);

        roofPillar = pillars.get(pillars.size()-1);
        //오른쪽에서 왼쪽으로
        for (int i = 1; i < pillars.size()-tallestPillarIndex; i++) {
            Pillar current = pillars.get(pillars.size()-i-1);
            if(roofPillar.height <= current.height) {
                int width = roofPillar.right - current.right;
                area += width * roofPillar.height;

                roofPillar = current;
            }
        }

        area += roofPillar.height;
        System.out.println(area);
    }

}
class Pillar {
    int left,right;
    int height;

    public Pillar(int left, int right, int height) {
        this.left = left;
        this.right = right;
        this.height = height;
    }

    @Override
    public String toString() {
        return "Pillar{" +
                "left=" + left +
                ", right=" + right +
                ", height=" + height +
                '}';
    }
}