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

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

2304번: 창고 다각형

 

다 풀고 나니 뭔가 괜히 어렵게 푼 것 같은 느낌이다.

 

가장 긴 기둥 찾기

이 문제는 가장 긴 기둥을 찾고, 처음과 끝 양쪽에서 해당 기둥까지 찾아가면 되는 문제이다. 이 때, 자기보다 작은 기둥은 무시하고 큰 기둥일 때만 길이를 바꿔준다.

 

한쪽 방향으로만 진행하면 쉽게 풀었을텐데, 양쪽에서 다가와야 하니 괜히 복잡하게 생각하다가 꼬인 코드를 제출했다. 원래는 스택의 가장 위에 있는 숫자보다 작으면 스택에 쌓이지 못하게 하고, 나중에 pop하면서 넓이를 계산하는 문제였겠지만, 나는 for문으로 풀게 되었다ㅎㅎ.... N이 최대 1000이라 시간 초과가 걸릴 일은 없었겠지만 무식한 풀이 방법이다.

 

끝에서부터 계산하는 넓이

끝부분은 앞부분과 다르게 조금 더 신경써야 한다. 기둥 하나가 1M의 폭을 갖고 있기 때문이다. 이 때문에 무작정 지난 위치를 빼주기만 하면 엉뚱한 결과가 나올 수 있다.

 

어떤 방법이 효율적인지는 모르겠지만, 나는 그냥 가장 긴 기둥이 나타날 때까지 그 전 기둥들의 위치 정보를 +1한 셈 치고 계산했다.

 백준에 있던 예시 그림인데, 주어진 기둥이 위와 같다면 8에 위치한 가장 긴 기둥에 닿을 때까지 15가 아니라 16, 13이 아니라 14로 계산해준 셈이다. 거꾸로 생각하면 된다.

 

전체 코드

public class Main {

	static class Node implements Comparable<Node>{
		int loc;
		int len;
		public Node(int loc, int len) {
			super();
			this.loc = loc;
			this.len = len;
		}
		
		@Override
		public int compareTo(Node o) {
			return this.loc - o.loc;
		}
		
		
	}
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int N = Integer.parseInt(br.readLine());
		
		Node[] arr = new Node[N];
		
		int max = 0;
		int max_loc = -1;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int loc = Integer.parseInt(st.nextToken());
			int len = Integer.parseInt(st.nextToken());
			
			if(max < len) {
				max = len;
				max_loc = loc;
			}
			
			arr[i] = new Node(loc, len);
		}
		
		Arrays.sort(arr);
		
		int h = arr[0].len;
		int past = arr[0].loc;
		int size = 0;
		for (int i = 1; i < N; i++) {
			if(arr[i].loc == max_loc) break;
			if(arr[i].len > h) {
				size += (arr[i].loc - past) * h;
				h = arr[i].len;
				past = arr[i].loc;
			}
		}
		
		size += (max_loc - past) * h;
		
		h = arr[N-1].len;
		past = arr[N-1].loc + 1;
		
		for (int i = N - 2; i >= 0; i--) {
			if(arr[i].loc == max_loc) break;
			if(arr[i].len > h) {
				size += (past - arr[i].loc - 1) * h;
				h = arr[i].len;
				past = arr[i].loc + 1;
			}
		}
		size += (past - max_loc - 1) * h;
		size += max;
		
		System.out.println(size);
	}

}