[백준] 전시장 - Java 2515

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

 

백준의 전시장 문제이다.

 

처음에는 문제를 읽자마자 그리디 문제인가 라는 생각이 들어서 그리디로 접근하려고 보니

 

입력의 단위가 굉장히 컸다. 즉, 이걸 그리디로 생각하여 특정 규칙을 정해 반복문을 돌리기에는 시간 초과가 우려됐다.

 

그래서, 이진 탐색으로 접근을 하려 시도하였다. 접근을 하니 이분 탐색의 키 값으로 돌릴 만한 것이

그림의 보이는 부분의 길이인 `S` 밖에 없었다.

 

그래서 최소값(left)으로 입력 받은 S를 정했고 가장 높은 값은 입력값중 가장 높은 `H`를 선택했다.

 

이렇게만 접근하니까 첫 번째 예제는 맞지만, 두 번째 예제에서 틀렸다.

 

그래서, 직접 그림을 그려보니 작성한 로직은 무조건 `mid`값 만큼 차이나면 그 값을 더하는 로직이였다.

 

하지만, 그렇게하는 것보다 `mid`만큼 차이나도 그걸 선택하지 않고 그 다음 값을 선택했을 때 더 커지는 경우가 있었다.

 

따라서, DP로 접근하였고 다음과 같은 점화식을 세웠다. `dp[i] = Math.max(dp[i - mid] + dp[i], dp[i - 1]);`

 

만약, `mid`값 전에 쌓여온 값이 존재하면 거기에 자신까지 더한 값이 클 것이고 그렇지 않으면,

해당 값을 선택하지 않은 경우의 값 중 큰 값을 선택하는 방식으로 했다.

 

 

public class BOJ2515 {
    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());

        int[][] arr = new int[N][2];

        int maxH = 0;
        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());

            int H = Integer.parseInt(st.nextToken());
            int C = Integer.parseInt(st.nextToken());

            arr[i][0] = H;
            arr[i][1] = C;

            maxH = Math.max(maxH, H);
        }

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

            return o1[0] - o2[0];
        }));

        int left = S;
        int right = maxH;

        int max = 0;

        while(left <= right){
            int mid = (left + right) / 2;
            int[] dp = new int[maxH + 1];

            for(int i = 0; i < N; i++){
                dp[arr[i][0]] = Math.max(arr[i][1], dp[arr[i][0]]);
            }

            for(int i = 1; i <= maxH; i++){
                if(i >= mid){
                    dp[i] = Math.max(dp[i - mid] + dp[i], dp[i - 1]);
                }
            }

            if(max <= dp[arr[N - 1][0]]){
                max = Math.max(dp[arr[N - 1][0]], max);
                right = mid - 1;
            } else{
                left = mid + 1;
            }

        }

        System.out.println(max);
    }
}