<Algorithm> 146. 상자넣기(BJO)

1. 1965번 상자넣기(BJO)

• DP를 이용하는 NlogN LIS문제

• 이문제는 배열의 인덱스를 이용하여 저장 변경을 활용하는 문제이다. 

• JAVA에서는 lowbound가 없어서 이부분을 조심해야 한다.

import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        sol(arr);
    }
    public static void sol(int arr[]) {
        int[] temp = new int[arr.length];// 서브시퀀스판단
        int[] result = new int[arr.length];// 가장긴 서브시퀀스판단
        int len = 0; // 서브시퀀스 최대 인덱스
        /******************************
         * DP를 이용한 LIS 알고리즘으로 (NlogN)
         * 최대 길이의 서브시퀀스를 구하고
         * 그 값이 하나의 박스로 넣을 수 있는 최대 수다
         *******************************/
        
        temp[len] = 0;
        Arrays.fill(result, -1);// -1은 앞에 아무것도 없다는 의미
        for(int i = 1; i < arr.length; i++) {
            if(arr[temp[len]] < arr[i]) {
                temp[++len] = i; // 배열의 인덱스를 저장
                result[i] = temp[len-1]; // 자신의 앞을 저장
            }else {
                idx = 0;
                lowBound(arr,temp, 0, len, arr[i]);
                //자신이 들어가야 할곳(찾은거 +1)
                if(idx > len) idx = len;
                temp[idx] = i;
                
                if(idx != 0)
                    result[i] = temp[idx-1];
            }
        }
        System.out.println(len+1);
        
    }
    static int idx;
    public static void lowBound(int[] arr,int[] temp,int start, int end, int target) {
        //System.out.println(start+" "+end);
        if(start>end) {
            idx = start+1;
            return;
        }else if(start == end) {
            idx = start;
            return;
        }
        int mid = (start + end) / 2;
        
        if(arr[temp[mid]] < target) {
            lowBound(arr, temp, mid+1, end, target);
        }else{
            lowBound(arr,temp, start, mid, target);
        }
    }
}
 

참고 & 출처  https://www.youtube.com/watch?v=CE2b_-XfVDk