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

📖 문제

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

 

 

 

💡  풀이 방식

•  브루트포스

 

가장 높은 길이를 기준으로 왼쪽 부분과 오른쪽 부분으로 나눠 지붕을 메꾼다.

 

1. 기둥들의 위치와 높이를 입력받는다.

2. 입력받은 기둥들의 정보를 위치 기준 오름차순 정렬한다.

3. 가장 높은 기둥의 길이를 기준으로 왼쪽 부분에서 기둥이 커지는 구간의 면적만 계산한다. (맨 왼쪽 0부터 pivot까지)

4. 가장 높은 기둥의 길이를 기준으로 오른쪽 부분에서 기둥이 작아지는 구간의 면적만 계산한다. (맨 오른쪽부터 pivot까지)

5. 제일 큰 기둥의 높이를 더한다.

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, sum;
    static List<Info> list = new ArrayList<>();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            
            int L = Integer.parseInt(st.nextToken());
            int H = Integer.parseInt(st.nextToken());
            
            list.add(new Info(L, H));
        }
        
        // 위치 기준 오름차순 정렬
        Collections.sort(list, (o1, o2) -> o1.x - o2.x);
        
        sum = 0;        // 창고 면적 누적 저장
        int pivot = 0;  // 가장 높은 기둥 높이
        
        // 1. 왼쪽 부분 계산 : [0, pivot]
        Info highC = list.get(0);    // 맨 왼쪽 끝 기둥
        for(int i = 1 ; i < list.size() ; i++) {
            Info curC = list.get(i);
            
            if(highC.high <= curC.high) {   // 더 높은 기둥을 만나면
                sum += (curC.x - highC.x) * highC.high;
                highC = curC;
                pivot = i;  // 가장 높은 기둥을  pivot으로
            }
        }
        
        // 2. 오른쪽 부분 계산 : [pivot, N-1]
        highC = list.get(list.size() - 1);  // 맨 오른쪽 끝 기둥
        for(int i = 1 ; i < list.size() - pivot ; i++) {
            Info curC = list.get(list.size() - 1 - i);
            
            if(highC.high <= curC.high) {
                sum += (highC.x - curC.x) * highC.high;
                highC = curC;
            }
        }
        
        // 3. pivot 기둥 넓이 더하기
        sum += list.get(pivot).high;
        
        System.out.println(sum);
    }
}
 
class Info {
    int x, C;  // x좌표, 높이
    
    public Info(int x, int C) {
        this.x = x;
        this.C = C;
    }
}

 

 

 

 

➕ 다른 풀이 방식

- 스택을 활용한 풀이!!

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

 

 

- 객체 배열 활용한 풀이! 그리고 설명도 굿!!

[백준 / JAVA] 2304번 창고 다각형

---

💦 어려웠던 점

- 한 방향으로만 이동하며 계산할 생각을 했었다...

- 뭔가 빗물 문제가 생각났다.

 

🧐 새로 알게 된 내용

- 가장 높은 높이 pivot을 기준으로 왼쪽 부분과 오른쪽 부분으로 나눠 계산하는 아이디어

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

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