<Algorithm> 210. 줄세우기(BOJ)

1. 2631번 줄세우기(BOJ)

   사용 알고리즘 :  LIS

• 이 문제는 처음에 문제를 잘못 이해해서 더 어렵게 느껴졌다. 아이가 서로 swap 되는 정렬이 아닌 단순히 이동시키는 것이었다.

• LIS라는 힌트를 보고 이미 순서대로 서있는 아이들을 제외한 아이들 모두 움직이는 것이 최소라는 것을 통해 풀 수 있었다.  

문제에 대한 접근&생각

1. 아이들의 순서를 오름차순, 이동 시킬 아이의 최소 -> 정렬? -> 최대 500명 -> DP!
2. 아이를 이동시킴 -> 이 뒤에 아이들은 밀림 -> 포함되지 않는 조건!
3. 이미 순서대로 있는 아이들 제외 한 나머지 아이들 이동 -> LIS! 

코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] temp = new int[n];
        int[] arr = new int[n];
        /***************************
         * LIS를 이용해 최대 길이를 구하고
         * 총 아이들에서 이값을 빼주어
         * 결과값을 출력한
         ***************************/
        int len = 0;
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        temp[0]=len;
        for(int i = 1; i < n ; i++) {
            if(arr[temp[len]] > arr[i]) {
                int idx = lowBound(0, len, arr[i], arr, temp);
                temp[idx] = i;
            }else {
                temp[++len] = i;
            }
        }
        System.out.println(n-(len+1));
    }
    private static int lowBound(int start, int end, int target,int[] arr, int[] temp) {
        if(start >= end)
            return start;
        
        int mid = (start + end)/2;
        
        if(arr[temp[mid]] < target) {
            return lowBound(mid+1, end, target,arr,temp);
        }else {
            return lowBound(start, mid, target,arr,temp);
        }
    }
}