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

www.acmicpc.net/problem/2304

2304번: 창고 다각형

1. 유형

구현

 

2. 자료구조

ArrayList

 

3. 구현기능

• 가장 긴 높이 찾기
• 오른쪽, 왼쪽 탐색해서 그 다음 높은 높이를 찾기

4. 풀이

 

왼쪽 탐색하는 코드. 오른쪽도 아래와 같은 코드를 구현하면 된다.

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {
	static int N;

	static class Pair {
		int pos;
		int h;

		public Pair(int pos, int h) {
			// TODO Auto-generated constructor stub
			this.pos = pos;
			this.h = h;
		}
	}

	static ArrayList<Pair> list;

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = Integer.valueOf(st.nextToken());
		list = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine());
			list.add(new Pair(Integer.valueOf(st.nextToken()), Integer.valueOf(st.nextToken())));
		}
		Collections.sort(list, new Comparator<Pair>() {
			@Override
			public int compare(Pair o1, Pair o2) {
				return o1.pos - o2.pos;
			}
		});
		int max = 0;
		int max_pos = 0;
		for (int i = 0; i < N; i++) {
			if (max < list.get(i).h) {
				max = list.get(i).h;
				max_pos = i;
			}
		}
		int sum =list.get(max_pos).h;
		int left_pos = max_pos;
		while (left_pos > 0) {
			Pair cur = list.get(left_pos);
			Pair next=null;
			int left_max = 0;
			for (int i = left_pos - 1; i >= 0; i--) {
				if (list.get(i).h > left_max) {
					left_max = list.get(i).h;
					left_pos = i;
					next = list.get(i);
				}
			}
			sum+= (cur.pos-next.pos)*next.h;
		}
		int right_pos = max_pos;
		while (right_pos < N-1) {
			Pair cur = list.get(right_pos);
			Pair next=null;
			int right_max = 0;
			for (int i = right_pos +1; i < N; i++) {
				if (list.get(i).h > right_max) {
					right_max = list.get(i).h;
					right_pos = i;
					next = list.get(i);
				}
			}
			sum+= (next.pos - cur.pos)*next.h;
		}
		System.out.println(sum);
	}
}

 

5. 느낀점

없음.