[BAEKJOON] 2631. 줄 세우기

 

문제링크

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

2631번: 줄세우기

 

백준 문제 '가장 긴 증가부분 수열' 문제와 유사한 문제

package acmicpc.Gold5;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class 줄_세우기 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		List<Integer> list = new ArrayList<>();
		list.add(-1);
		
		for(int i = 0 ; i < n ; i++) {
			int x = Integer.parseInt(br.readLine());
			
			if(list.get(list.size() - 1) < x) list.add(x);
			else {
				int low = 0;
				int high = list.size() - 1;
				
				while(low < high) {
					int mid = (low + high) / 2;
					
					if(list.get(mid) > x) {
						high = mid;
					} else {
						low = mid + 1;
					}
				}
				list.set(low, x);
			}
		}
		System.out.println(n - list.size() + 1);
	}
}