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

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

2304번: 창고 다각형

<문제 분석>
1. N개의 막대기둥이 늘어서있다. 폭은 모두 1m이다.
2. 막대기둥을 다 덮을 지붕을 만들어야 한다.
  - 지붕은 각 기둥의 윗면과 닿아야 한다.
  - 지붕은 어떤 기둥의 옆면과 닿아야 한다.

<1차 풀이>
1. class point { int x, int y } 선언한다.
2. 배열로 입력받은 기둥을 삽입한다.
3. stack으로 비교 함수를 만든다.
  - 첫 기둥을 스택에 넣는다.
  - stack.peek()을 해서 다음 기둥과 비교한다.
  - 다음 기둥이 스택의 기둥보다 낮으면 스킵한다.
  - 높으면 stack.pop해서 넓이 계산해서 sum에 더하고 새 기둥은 push한다.
  - 계속 낮은 기둥이 나오고 마지막 기둥까지 낮으면 높은 기둥의 넓이는 따로 계산한다.
  - 마지막 기둥까지의 넓이도 따로 계산해서 더한다.

아이디어 구상 : 17분
코드 구현 : 28분 - 샘플예제는 맞았으나 제출 시 실패

 

<2차 풀이 >

 

문제를 보면 가장 높은 기둥을 기준으로 첫 기둥에서 그 기둥까지의 넓이를 구하고, 마지막 기둥에서 그 기둥까지의 넓이를 구하면 된다. 굳이 스택을 사용할 필요도 없이 ArrayList로 구현이 가능하다. 가장 높은 기둥이 처음에 올 수도 있고, 마지막에 올수도 있지만 구현에는 큰 문제가 없다. 앞에서 뒤로, 뒤에서 앞으로 넓이를 구하기 때문에 무조건 커버가 된다.

그리고, 마지막에 최고 높은 기둥의 넓이를 더해주면 된다.

 

0. 입력함수에서 maxH의 값을 구한다.

1. L을 오름차순으로 정렬한다.
2. 가장 높은 기둥의 인덱스를 구한다.(maxL)
3. 0 to maxL까지의 넓이를 구한다. (좌 -> maxL)
4. N-1 to maxL까지의 넓이를 구한다. (maxL <- 우)
5. 마지막에 3과 4 결과에 maxH를 더해준다.

 

<코드 구현>

import java.util.Scanner;
import java.lang.Comparable;
import java.util.ArrayList;
import java.util.Collections;
import java.lang.Math;


//[백준] 2304번 - 창고 다각형 (Java)

public class Main {
    static int N;
    static int maxH, maxL;
    static ArrayList<Build> list = new ArrayList<>();

    class Build implements Comparable<Build> {
        int L, H;
        Build (int L, int H) {
            this.L = L;
            this.H = H;
        }
        @Override
        public int compareTo(Build o) {
            return this.L - o.L;
        }
    }
    
    public void InputData() {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        for (int i=0; i<N; i++) {
            int l = sc.nextInt();
            int h = sc.nextInt();
            list.add(new Build(l, h));
            maxH = Math.max(maxH, h);
        }
    }

	public void Solve() {
        int sum = 0;
        // 1. L 오름차순으로 정렬
        Collections.sort(list);

        // 2. 가장 높은 기둥의 위치L 구하기
        for(int i=0; i<list.size(); i++) {
            if (list.get(i).H == maxH) {
                maxL = i;
                break;
            }
        }

        // 3. 0 to maxH까지 넓이 구하기
        for (int i=0; i<maxL; i++) {
            for (int j=i+1; j<=maxL; j++) {
                if (list.get(i).H <= list.get(j).H) {
                    sum += (list.get(j).L - list.get(i).L) * list.get(i).H;
                    i = j;
                }
            }
        }

        // 4. N-1 to maxH까지 넓이 구하기
        for (int i=N-1; i>maxL; i--) {
            for (int j=i-1; j>=maxL; j--) {
                if (list.get(j).H >= list.get(i).H) {
                    sum += (list.get(i).L - list.get(j).L) * list.get(i).H;
                    i = j;
                }
            }
        }

        // 5. 가장 높은 막대의 넓이도 더하기
        System.out.println(sum + maxH);
	}
    
	public static void main(String[] args)
	{
		Main m = new Main();
		m.InputData();///입력
		//코드를 작성하세요
        m.Solve();
	}
}

 

<제출 결과>