[BOJ] 2304 창고다각형 - JAVA

1. 문제

2304번: 창고 다각형

N 개의 막대 기둥이 일렬로 세워져 있다. 기둥들의 폭은 모두 1 m이며 높이는 다를 수 있다. 이 기둥들을 이용하여 양철로 된 창고를 제작하려고 한다. 창고에는 모든 기둥이 들어간다. 이 창고의 지붕을 다음과 같이 만든다.

1. 지붕은 수평 부분과 수직 부분으로 구성되며, 모두 연결되어야 한다.
2. 지붕의 수평 부분은 반드시 어떤 기둥의 윗면과 닿아야 한다.
3. 지붕의 수직 부분은 반드시 어떤 기둥의 옆면과 닿아야 한다.
4. 지붕의 가장자리는 땅에 닿아야 한다.
5. 비가 올 때 물이 고이지 않도록 지붕의 어떤 부분도 오목하게 들어간 부분이 없어야 한다.

그림 1은 창고를 옆에서 본 모습을 그린 것이다. 이 그림에서 굵은 선으로 표시된 부분이 지붕에 해당되고, 지붕과 땅으로 둘러싸인 다각형이 창고를 옆에서 본 모습이다. 이 다각형을 창고 다각형이라고 하자.

그림1 . 기둥과 지붕(굵은 선)의 예

창고 주인은 창고 다각형의 면적이 가장 작은 창고를 만들기를 원한다. 그림 1에서 창고 다각형의 면적은 98 ㎡이고, 이 경우가 가장 작은 창고 다각형이다.

기둥들의 위치와 높이가 주어질 때, 가장 작은 창고 다각형의 면적을 구하는 프로그램을 작성하시오.

---

2. 풀이

• 기둥을 위치 순으로 정렬한다.
• area 변수에 면적을 저장해서 마지막에 출력한다.
• 기둥 수 만큼 반복하면서 다음을 수행한다.
  • i는 현재 기둥, j는 현재 기둥 바로 다음부터 끝까지의 시작하는 기둥 중 하나다.
  • 현재 기둥(i)높이보다 탐색기둥(j)가 더 높을 때까지 j에 1씩 더해가면서 탐색한다. 이 과정에서 i기둥보다 크지않은 max값이 몇번째 기둥인지 파악해둔다.
  • j가 N보다 크거나 같다면 i번째 기둥보다 큰 기둥이 없는 경우다.
    • 따라서 i 다음으로 가장 큰 max 기둥을 이용한다.
    • i번째 기둥 높이 + (max기둥위치-i기둥위치-1=가로)*다음 기둥 높이 를 area에 저장한다.
    • 새로운 i값으로 다음 기둥 인덱스(max)를 설정한다.

• j가 N보다 작다면 i번째 기둥보다 큰 기둥이 있는 경우다.
  • i번째 기둥 높이*(j번째 기둥위치-i번째 기둥위치)를 area에 저장한다.
  • 새로운 i값으로 다음 기둥 인덱스(j)를 설정한다.

import java.io.*;
import java.util.*;

public class BOJ_2304_창고다각형 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      int N = Integer.parseInt(in.readLine());
      StringTokenizer st;

      int[][] col = new int[N][2];
      for (int i = 0; i < N; i++) {
         st = new StringTokenizer(in.readLine());
         col[i][0] = Integer.parseInt(st.nextToken());//위치
         col[i][1] = Integer.parseInt(st.nextToken());//높이
      }

      Arrays.sort(col, (o1, o2) -> o1[0] - o2[0]);

      int area = 0;
      for(int i=0;i<N;){
         int j=i+1; int max = j;
         while(j<N && col[i][1]>col[j][1]){
            if(col[max][1]<col[j++][1]) max = j-1;
         }

         if(j>=N){
            area+=col[i][1];
            if(max<N) area+=col[max][1]*(col[max][0]-col[i][0]-1);
            i=max;
         }else{
            area+= col[i][1]*(col[j][0]-col[i][0]);
            i=j;
         }

      }
      System.out.println(area);
   }
}

 

---

3. 결과

처음풀었을 때보다 코드가 더 깔끔해졌다. 이게 더 맘에 든다. ㅎㅎ