[백준 2515] 전시장

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

2515번: 전시장

dp를 적용하여 풀이할 수 있다.

문제에서 제시한 테스트케이스 1번을 통하여 생각해 보면

6 4
//그림 입력
15 80
8 230
10 100
17 200
20 75
26 80

 

위에서 입력된 그림들을 높이 asc, 비용 desc 기준으로 정렬하면 다음과 같다.

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

 

높이가 제일 낮은 그림 (8,230)을 고르는 경우를 생각해 보면

두번째 그림의 높이는 10이므로 첫번째 그림과의 간격이 부족하여 선택할 수 없다. 따라서 높이가 15인 그림부터 선택할 수 있다

이런 과정을 그림을 통하여 생각하면 다음과 같다

 

위의 트리(?)에서, (15,80)을 선택하는 경우와 (17,200)을 선택하는 경우 두 가지로 나뉠 수 있다.

비용의 최대를 구하는 게 목적이므로, 두 경우의 총 합 중 더 큰 값을 가지는 (17,200)을 선택하여 (8,230)을 선택하는 경우의 최대를 갱신할 수 있다.

 

 

 

위의 과정을 쉬운 구현을 위해 

maxCost(dp array)를

maxCost[i] = 0~i 까지의 그림을 고려했을 때의 최대

로 정의하여 풀이함.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

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

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input = br.readLine();
		N = Integer.parseInt(input.split(" ")[0]);
		S = Integer.parseInt(input.split(" ")[1]);

		int[][] arts = new int[N][2];
		for (int i = 0; i < N; i++) {
			arts[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		}

		//높이 asc, 비용 desc
		Arrays.sort(arts, (o1, o2) -> {
			if (o1[0] == o2[0])
				return o2[1] - o1[1];
			return o1[0] - o2[0];
		});
		maxCost = new int[N];
		int[] sortedHeights = Arrays.stream(arts).mapToInt(i -> i[0]).toArray();
		//dp
		maxCost[0] = arts[0][1];
		for (int i = 1; i < N; i++) {
			int currHeight = arts[i][0];
			int currCost = arts[i][1];
			int findIdx = Arrays.binarySearch(sortedHeights, currHeight - S);
			if (findIdx != -1) {
				if (findIdx < 0) {
					findIdx = -(findIdx + 1) - 1;
				}
				maxCost[i] = maxCost[findIdx] + currCost;
			} else {
				maxCost[i] = currCost;
			}
			maxCost[i] = Math.max(maxCost[i - 1], maxCost[i]);
		}

		System.out.println(maxCost[maxCost.length - 1]);
	}
}