[백준 / BOJ] 2515번 : 전시장 (JAVA)

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

2515번: 전시장

현재 미술품 높이 - S 이하 중 가장 큰 값 찾기

작은 것부터 전시하는 것이 더 합리적이기 때문에, 일단 입력을 받은 후에 높이 순으로 정렬을 진행했다. 그리고 cost라는 배열을 만들어서 각 순서의 가장 큰 값을 저장하도록 했다.

 

i번째 미술품을 게산할 때에는 i번째 미술품의 높이 - S 값 중 최댓값을 찾았다. 이를 위해 이분 탐색을 사용했다. while문을 돌린 후 end값이 조건 내에서 최댓값을 가리키기 때문이다.

 

해당 최댓값의 cost에 현재 cost를 더한 값이 i번째 미술품까지 계산하고, i번째 미술품을 전시하기로 했을 때 가장 큰 값이다. 이 미술품을 올리지 않아도 된다. 이를 위해 i - 1번째 값과 비교하여, 둘 중 더 큰 값을 현재 cost에 저장하도록 했다. 

// 시간 : 1260ms
// 메모리 : 97516KB
public class Main {

	static class Node implements Comparable<Node> {
		int h;
		int c;
		
		public Node(int h, int c) {
			super();
			this.h = h;
			this.c = c;
		}
		@Override
		public int compareTo(Node o) {
			int n = this.h - o.h;
			if(n != 0) return n;
			else return o.c - this.c;
		}
		
		
	}
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int S = Integer.parseInt(st.nextToken());
		
		Node[] art = new Node[N];
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			
			int H = Integer.parseInt(st.nextToken());
			int C = Integer.parseInt(st.nextToken());
			
			art[i] = new Node(H, C);
		}
		
		Arrays.sort(art);
		
		long[] cost = new long[N];
		cost[0] = art[0].c;
		
		long max = cost[0];
		
		for (int i = 1; i < N; i++) {
			int start = 0;
			int end = i - 1;
			
			while(start <= end) {
				int mid = (start + end) / 2;
				if(art[mid].h < art[i].h - S) {
					start = mid + 1;
				} else if(art[mid].h > art[i].h - S) {
					end = mid - 1;
				} else {
					end = mid;
					break;
				}
			}
			if(end == -1) {
				cost[i] = Math.max(cost[i - 1], art[i].c);
			} else if(art[end].h <= art[i].h - S) {
				cost[i] = cost[end] + art[i].c;
			}
			
			cost[i] = Math.max(cost[i], cost[i-1]);
			max = Math.max(max, cost[i]);
		}
		
		System.out.println(max);
	}

}