백준 2515 : 전시장

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

2515번: 전시장

[ 문제풀이 ]

최적화 문제는 그리디, DP, 파라메트릭 서치 중 하나라고 생각하기 때문에 이 문제 역시 이들을 기반으로 접근하였다.

먼저 그리디이다. 그리디는 매 순간의 선택이 최적해라는 것이 보장되어야 하는데 이는 성립하지 않는다는 것을 반례를 통해 쉽게 찾을 수 있다.

다음으로 파라메트릭 서치이다. 구하고자 하는 금액을 이분 탐색을 시도하면서 진행해야 하는데 현재 key값인 금액이 가능한지를 판단하는 로직을 구현하기가 상당히 까다롭다.

따라서 이 문제는 DP를 활용하여 해결하였다.

 

먼저 그림들을 높이 순으로 정렬하고 dp 테이블을 다음과 같이 정의하자.

dp[i][0] : i번째 그림을 설치했을때 최대값
dp[i][1] : i번째 그림을 설치하지 않았을때 최대값

 

점화식은 어떻게 될까? dp[i][1]은 간단하다. 현재 그림을 설치하지 않으니 현재 그림 이전에 구해온 최댓값을 뽑아주면 된다.

그렇다면 dp[i][0]는 어떻게 구해야 할까? i번째 그림을 설치하기 위해선 (i번째 그림의 높이 - S)의 높이보다 큰 높이를 가지는 그림은 설치해서는 안된다.

즉, 우리는 (i번째 그림의 높이 - S)의 높이를 가지는 그림의 위치를 찾은 다음, 해당 위치의 dp값에 i번째 그림을 설치해주는 비용을 추가해주면 된다.

근데 N이 최대 30만이기 때문에 i-1번째부터 1번까지 순차 탐색으로 위치를 찾는다면 최악의 경우 O(N^2)이기 때문에 TLE가 발생한다.

 

탐색의 시간 복잡도를 줄여야 하는데 잘 생각해보면 그림을 높이 순으로 정렬하였다. 정렬된 상태에서 사용할 수 있는 빠른 탐색기법이 있지 않은가?

바로 이분 탐색을 활용하면 O(NlogN)만에 해결할 수 있게 된다.

다만, 이분 탐색은 key값이 존재해야지만 탐색해주기 때문에 이분 탐색을 응용한 upperBound로 찾아준다. upperBound는 key보다 큰 값의 첫 번째 위치를 찾아주기 때문에 구하고자 하는 위치는 (upperBound 결과 - 1)임을 알 수 있다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	static int N, S;
	static int[][] draw;

	public static void main(String[] args) {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			S = Integer.parseInt(st.nextToken());
			draw = new int[N + 1][2];
			for (int i = 1; i <= N; ++i) {
				st = new StringTokenizer(br.readLine());
				draw[i][0] = Integer.parseInt(st.nextToken());
				draw[i][1] = Integer.parseInt(st.nextToken());
			}

			Arrays.sort(draw, 1, N + 1, (o1, o2) -> o1[0] - o2[0]);
			/**
			 * dp[i][0] : i번째 그림을 설치했을때 최대값
			 * dp[i][1] : i번째 그림을 설치하지 않았을때 최대값
			 */
			int[][] dp = new int[N + 1][2];
			dp[1][0] = draw[1][1];
			for (int i = 2; i <= N; ++i) {
				int idx = upperBound(1, i, draw[i][0] - S);
				
				if (idx == i + 1) dp[i][0] = draw[i][1];
				else dp[i][0] = Math.max(dp[idx - 1][0], dp[idx - 1][1]) + draw[i][1];
				dp[i][1] = Math.max(dp[i - 1][0], dp[i - 1][1]);
			}
			bw.write(Math.max(dp[N][0], dp[N][1]) + "\n");
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

	public static int upperBound(int l, int r, int key) {
		while (l < r) {
			int m = (l + r) >> 1;
			if (draw[m][0] <= key) l = m + 1;
			else r = m;
		}
		return r;
	}
}