Algorithm/Java
[백준/Java] 2304번 : 창고 다각형
_윤
2024. 2. 15. 21:17
728x90
[문제]
N 개의 막대 기둥이 일렬로 세워져 있다. 기둥들의 폭은 모두 1 m이며 높이는 다를 수 있다. 이 기둥들을 이용하여 양철로 된 창고를 제작하려고 한다. 창고에는 모든 기둥이 들어간다. 이 창고의 지붕을 다음과 같이 만든다.
- 지붕은 수평 부분과 수직 부분으로 구성되며, 모두 연결되어야 한다.
- 지붕의 수평 부분은 반드시 어떤 기둥의 윗면과 닿아야 한다.
- 지붕의 수직 부분은 반드시 어떤 기둥의 옆면과 닿아야 한다.
- 지붕의 가장자리는 땅에 닿아야 한다.
- 비가 올 때 물이 고이지 않도록 지붕의 어떤 부분도 오목하게 들어간 부분이 없어야 한다.
그림 1은 창고를 옆에서 본 모습을 그린 것이다. 이 그림에서 굵은 선으로 표시된 부분이 지붕에 해당되고, 지붕과 땅으로 둘러싸인 다각형이 창고를 옆에서 본 모습이다. 이 다각형을 창고 다각형이라고 하자.
창고 주인은 창고 다각형의 면적이 가장 작은 창고를 만들기를 원한다. 그림 1에서 창고 다각형의 면적은 98 ㎡이고, 이 경우가 가장 작은 창고 다각형이다.
기둥들의 위치와 높이가 주어질 때, 가장 작은 창고 다각형의 면적을 구하는 프로그램을 작성하시오.
[조건]
- 시간 제한 : 2초
- 메모리 제한 : 128MB
[입력]
첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 빈 칸을 사이에 두고 주어진다. L과 H는 둘 다 1 이상 1,000 이하이다.
[출력]
첫 줄에 창고 다각형의 면적을 나타내는 정수를 출력한다.
[문제 풀이]
- 가장 높은 기둥이 중간에 있을 것을 고려
- 왼쪽에서부터 최장 기둥, 오른쪽에서 최장 기둥의 상황을 나누어 구함
import java.util.*;
import java.io.*;
public class Main {
static BufferedReader br;
static StringTokenizer st;
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int max = Integer.MIN_VALUE;
int maxIdx = 0;
int res = 0;
Map<Integer, Integer> map = new HashMap<>();
// L : key, H : value
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
int key = Integer.parseInt(st.nextToken());
int value = Integer.parseInt(st.nextToken());
map.put(key, value);
if(value>max) {
max = value;
}
}
// key값 기준 정렬
List<Integer> keyList = new ArrayList<>(map.keySet());
Collections.sort(keyList);
// 빌딩 높이 중 최댓값 찾아 해당 인덱스 반환
for(int i=keyList.size()-1; i>=0; i--) {
if(map.get(keyList.get(i))==max) {
maxIdx = i;
break;
}
}
int now = map.get(keyList.get(0)); // 현재 최장 높이
for(int i=0; i<maxIdx; i++) {
int num = map.get(keyList.get(i)); // 지금 높이
int next = map.get(keyList.get(i+1)); // 다음 높이
res+=((keyList.get(i+1)-keyList.get(i))*now);
if(num<next && now<next) { // 만약 다음 기둥의 높이가 현재 기둥보다 높고, 현재 최장 기둥보다 높다면 갱신
now = next;
}
}
now = map.get(keyList.get(keyList.size()-1));
for(int i=keyList.size()-1; i>maxIdx; i--) {
int num = map.get(keyList.get(i));
int next = map.get(keyList.get(i-1));
res+=((keyList.get(i)-keyList.get(i-1))*now);
if(num<next && now<next) {
now = next;
}
}
res+=map.get(keyList.get(maxIdx)); // 최대의 높이는 안더해져서 따로 더해줌
System.out.println(res);
}
}
[소감]
- 특정 상황을 고려하지 못했음
- 직접 여러 TC를 만들어 고민했으나 반례를 찾지 못하였고 도움을 얻은 반례 아래 첨부
8
1 10
2 50
3 40
4 30
5 40
6 30
7 50
8 100
728x90
반응형