[Java] 2516 전시장 - Binary Search, DP

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

2515번: 전시장

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
 
/**
 *
 */
public class bj2516 {
    static int[][] paint;
    static int N, S;
    static int[][] DP;
    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());
        S = Integer.parseInt(st.nextToken());
        paint = new int[N+1][2];
        for(int n=1;n<=N;n++){
            st = new StringTokenizer(br.readLine());
            paint[n][0] = Integer.parseInt(st.nextToken());
            paint[n][1] = Integer.parseInt(st.nextToken());
        }
        // 가장 긴 증가하는 수열 찾기 문제랑 비슷하다고 생각했고..
        // ->> 어짜피 그림 위치는 바꿀 수 있고 가장 많이 보이려면 어찌됐든 오름차순으로 보여야 되니까
        // 입력이 상대적으로 많으니까 가장 긴 증가하는 수열에서 시간을 줄이기 위해 썼던 방법인 이분탐색을 활용함.
 
        Arrays.sort(paint, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0] == o2[0]) return o2[1]-o1[1];
                else return o1[0]-o2[0];
            }
        });
        //높이는 오름차순, 가격은 내림차순으로 정렬.
 
        /*
        for(int[] a : paint){
            for(int k : a){
                System.out.print(k + " ");
            }
            System.out.println();
        }
        */
        DP = new int[N+1][2];
        for (int n = 1; n <= N; n++) {
            if (paint[n][0] - DP[n - 1][1] >= S) { //차이가 S이상이면 일단 더함.
                DP[n][0] = DP[n - 1][0] + paint[n][1]; //최고 금액 저장.
                DP[n][1] = paint[n][0]; // 직전 추가된 높이 저장.
            } else {
                int prev; // n과의 높이 차이가 S이상인 지점
                prev = binary_search(n);
                if (DP[n - 1][0] > DP[prev][0] + paint[n][1]) { //현재 그림을 선택하지 않는 경우
                    DP[n][0] = DP[n - 1][0];
                    DP[n][1] = DP[n - 1][1];
                } else { //현재 그림을 선택하는 경우
                    DP[n][0] = DP[prev][0] + paint[n][1];
                    DP[n][1] = paint[n][0];
                }
            }
            for(int i=0;i<DP.length;i++){
                System.out.print(Arrays.toString(DP[i]));
            }
            System.out.println();
        }
        System.out.println(DP[N][0]);
 
    }
 
    public static int binary_search(int n){
        int low = 0;
        int high = n - 1;
 
        while (low <= high){
            int mid = (low + high) / 2;
            if (paint[n][0] - paint[mid][0] >= S) low = mid + 1;
            else high = mid - 1;
        }
        return high;
    }
}

[풀이]

위에도 말했다시피 가장 긴 증가하는 수열 (LIS) 문제를 응용해서 이분 탐색을 해야겠다고 생각했다.

같은 스터디를 하는 오빠 한분이 전시장의 모든 길이를 포함하는 배열을 만들어 빈 공간을 DP[idx-1]로 채워주는 형식의 선형 방법을 통해

인덱스를 저장해줬는데 훠어어어얼씬 시간이 적게 나와서 신기했다.

또 다른 오빠 한분은 직접 이분탐색을 구현하는 대신 binarysearch라는 메소드를 사용했는데, 이 메소드의 경우 bound를 사용할 수 없다고 한다. 따라서 이 때 메소드의 값이 마이너스가 되는 것을 방지하기 위해 마이너스가 될 겨우 2를 빼고 부호를 변경해주는 방법을 사용했는데, 굉장히 신선했다. 

 

이런거 써도 되나 싶지만 어짜피 내 티스토리는 나만 본당 ㅎ

헿

그럼 끝!!