[백준] BOJ 2515 전시장 (골드 2)

문제

---

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

2515: 전시장

---

해설

---

1. 그림을 높이 기준 오름차순으로 정렬한다.
2. DP 테이블 : 해당 높이까지 선택한 조합의 가장 큰 값 갱신dp[i] = Math.max(dp[i - 1], dp[upperBound - 1] + 현재 그림의 가치)
   이를 통해 [이전까지의 최대값과] 현재 [그림의 가치 + S만큼 떨어진 그림까지의 최대 가치] 중 더 큰 값으로 갱신된다.
3. 하나씩 확인하며 해당 높이 - S보다 큰 첫번째 인덱스 (UpperBound)를 찾는다.해당 인덱스 - 1이 높이 - S 보다 작은 값 중 가장 큰 높이이다.
   upperBound 사용 이유 : 타겟 높이보다 큰 가장 첫번째 요소의 인덱스를 반환하지만
   필요한 것은 해당 인덱스 바로 전 (즉, 타겟 높이보다 작은 가장 마지막 요소를 이용하기 위함)
4. 따라서 위의 과정을 통해 dp[N]에 최대값이 갱신되어 이를 출력한다.

---

추가 정리

---

추가적으로 정렬 시 cost도 정렬해야할까 했지만,upperBound에서 사용하는 것은 높이만 이용하며,
같은 높이는 dp[i] = Math.max(dp[i - 1], dp[upperBound - 1] + 현재 그림의 가치) 이다.

만약, 높이가 같은 그림 8 20, 8 30이 순서가 보장되어 있지 않아도
8 20를 확인시 최대 가치가 30(이전 10 + 현재 20)일때
8 30을 확인시 최대 가치가 30(이전 10 + 현재 30)이 되어
해당 높이의 최대 값이 갱신된 상태가 된다.

이 상태에서 upperBound - 1을 사용하면 target보다 작은 가장 마지막
(여기서는 8 30의 인덱스)를 반환하므로 문제가 없다.

즉, 순서가 8 30, 8 20 인 경우 dp의 두 인덱스는 모두 8 30기준으로 갱신됨.

---

코드 (DP, 정렬, 이분 탐색)

---

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

public class BOJ2515 {
    static int[][] pictures;
    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        int S = Integer.parseInt(st.nextToken());

        pictures = new int[N + 1][2];
        pictures[0] = new int[]{Integer.MIN_VALUE, 0};
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            int h = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            pictures[i] = new int[]{h, c};
        }

        Arrays.sort(pictures, (o1, o2) -> {
            if(o1[0] == o2[0]) return Integer.compare(o2[1], o1[1]);
            return Integer.compare(o1[0], o2[0]);
        });

        int[] dp = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            int[] picture = pictures[i];

            int idx = upperBound(picture[0] - S) - 1;
            dp[i] = Math.max(dp[i - 1], dp[idx] + picture[1]);
        }
        System.out.println(dp[N]);
    }

    private static int upperBound(int target) {
        int l = 1;
        int r = N;

        while (l <= r) {
            int mid = (l + r) / 2;

            if (pictures[mid][0] <= target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }
}

---

결론

---

DP 열심히 공부하자!

---