백준 2515번 : 전시장 [Java]

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

 

문제 탐색하기

문제는 전시대에 그림을 폭을 겹쳐서 놓는다. 이때 관람자가 보이는 그림의 폭이 S 이상인 그림만 살 수 있고 이 때 모든 그림의 값의 최대 합을 구하는게 목표다. 처음에 들여다 봤을 때는 모두 탐색하는게 답이지 않을까? 라고 생각할 수 있는데 그렇지 않다. 입력을 보게되면 N이 최대 30만이므로 O(N ^ 2)으로 탐색하게 되면 최대 900억번 반복 탐색해야하므로 1초의 시간 제한 안에 들어올 수 없을 것이다. 그래서 우리는 다른 방법을 찾아야만 한다.

 

입력이 크므로 시간 복잡도를 낮춰서 최소 한번은 N을 탐색하더라도 나머지 숫자를 log를 사용하게 만들던 해야 시간 복잡도를 통과할 수 있으리라 짐작된다. 그려면 어떤 식으로 탐색할 수 있을까? 모든 그림을 순서대로 배열하면 해당 값을 포함하는 최대합을 구할 수 있다. 이 때 차이가 S보다 큰 경우에서 모든 경우의 수를 더하지 말고 특정 수들만 더하게 해서 시간 복잡도를 낮출 수 있다. 다음 예제를 통해서 확인해보자

8    10   15  17   20  26
230  100  80  200  75  80

S = 4

 

높이가 8인 그림을 가지고 최대합을 만들 수 있는 경우는 어떻게 탐색할 수 있을까?

8 - 15 - 20 - 26

8 - 17 - 26

 

위와 같은 방식으로 S보다 크게 이동하도록 하여서 찾을 수 있다. 그러면 이 S만큼 차이나는 부분을 이분탐색을 통해서 인덱스를 파악하면 된다.

어떤 그림에 높이가 8인 그림을 더해야 할까?

우리가 구하는 높이의 그림을 x라고 하고 위의 이분탐색을 통해서 구한 인덱스에 해당하는 높이를 h라고 한다면 아래와 같은 식을 세워볼 수 있다.

h - S < x < h + S

 

위 식을 벗어난다면 x와 다른 수의 크기가 S보다 커지게 되므로 최대합을 구할 때 비효율적이다. (모든 수를 다 따져봐야하기 때문이다.) 모든 수를 다 더해야한다면 완전 탐색과 별반 다르지 않은 시간 복잡도를 얻게 된다.

 

코드 구현하기

1. 입력을 처리하고 저장할 dp값을 불러온다. 그림이라는 클래스를 통해서 높이와 가격을 한번에 리스트에 저장할 수 있도록 만든다.
2. 리스트를 높이 순으로 정렬하여 이분 탐색에 사용할 수 있도록 한다.
3. dp값에 그림의 모든 초기 가격을 저장한다. 초기 가격이 최대값일 수도 있다.
4. 반복문을 통해서 아래를 구현한다.
   1. 이분 탐색을 통해서 현재 인덱스 보다 큰 부분에서 + S와 근접한 높이를 가진 그림의 인덱스를 찾는다.
   2. 해당 인덱스를 통해서 h - S < x < h + S를 만족하는 target에 대해서 현재 그림의 가격을 더하고 비교하여 최대 값을 찾는다.
5. 모든 dp배열을 탐색하여 최대값을 찾는다.

풀이

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

public class Main {
	public static class FastReader {
	    BufferedReader br;
	    StringTokenizer st;

	    public FastReader() {
	        br = new BufferedReader(new InputStreamReader(System.in));
	    }

	    String next() {
	        while (st == null || !st.hasMoreElements()) {
	            try {
	                st = new StringTokenizer(br.readLine());
	            } catch (IOException e) {
	                e.printStackTrace();
	            }
	        }

	        return st.nextToken();
	    }

	    int nextInt() {
	        return Integer.parseInt(next());
	    }

	    long nextLong() {
	        return Long.parseLong(next());
	    }

	    double nextDouble() {
	        return Double.parseDouble(next());
	    }
	}

	static int N, S;
	static int[] dp;
	static ArrayList<Drawing> drawings = new ArrayList<>();
	static HashMap<Integer, Integer> inputs = new HashMap<>();

	static class Drawing {
		int height, price;

		public Drawing(int height, int price) {
			this.height = height;
			this.price = price;
		}

		@Override
		public String toString() {
			return " " + price + " " + height + " ";
		}
	}


	public static void main(String[] args) {
		FastReader fr = new FastReader();
		N = fr.nextInt();
		S = fr.nextInt();

		for (int i = 0; i < N; i++) {
			int h = fr.nextInt();
			int p = fr.nextInt();
			int temp = inputs.getOrDefault(h, 0);
			inputs.put(h, Math.max(p, temp));
		}

		for (int key : inputs.keySet()) {
			drawings.add(new Drawing(key, inputs.get(key)));
		}

		dp = new int[drawings.size()];

		Collections.sort(drawings, Comparator.comparing(o -> o.height));

		int result = 0;
		dp[0] = drawings.get(0).price;

		int l = drawings.size();
		for (int i = 0; i < l; i++) {
			dp[i] = drawings.get(i).price;
		}
		for (int i = 0; i < l; i++) {
			int low = i + 1;
			int high = l;
			int mid = 0;

			while (low < high) {
				mid = (low + high) / 2;
				if (Math.abs(drawings.get(i).height - drawings.get(mid).height) >= S) {
					high = mid;
				} else {
					low = mid + 1;
				}
			}

			int target = low;
			if (low == l) {
				continue;
			}
			while (drawings.get(low).height - S < drawings.get(target).height && target > i && drawings.get(target).height - drawings.get(i).height >= S) {
				dp[target] = Math.max(dp[target], dp[i] + drawings.get(target).price);
				target--;
			}

			target = low;
			while (drawings.get(low).height + S > drawings.get(target).height) {
				dp[target] = Math.max(dp[target], dp[i] + drawings.get(target).price);
				target++;

				if (target == l) {
					break;
				}
			}
		}

		for (int i = 0; i < l; i++) {
			result = Math.max(dp[i], result);
		}

		System.out.println(result);
	}
}