728x90
https://www.acmicpc.net/problem/2631
메모리: 14,132 KB , 시간: 100 ms
사용 알고리즘: 다이나믹 프로그래밍, 최장 증가 부분 수열(LIS)
728x90
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.LinkedList; public class Main { public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); int[] arr = new int[N]; for (int i = 0; i < N; i++) { arr[i] = Integer.parseInt(br.readLine()); } // 가장 긴 증가하는 부분 수열(LIS) LinkedList<Integer> lis = new LinkedList<>(); lis.add(arr[0]); int s, e, m, tmp; for (int i = 1; i < N; i++) { // lis의 마지막 원소보다 더 크다면 바로 넣어줌 if(lis.get(lis.size() - 1) < arr[i]) lis.add(arr[i]); else { // 이분 탐색 -> arr[i]보다 큰 수 중 가장 작은 수 구하기 s = 0; e = lis.size() - 1; tmp = 0; while(s <= e) { m = (s + e) / 2; if(lis.get(m) > arr[i]) { tmp = m; e = m - 1; } else s = m + 1; } // 이분 탐색으로 찾은 자리에 arr[i]를 대신 넣어줌 lis.set(tmp, arr[i]); } } // 가장 긴 증가하는 부분 수열은 고정 // 이외의 수들은 자리를 옮겨야 함 System.out.println(N - lis.size()); } }
728x90
'Problem Solving > BOJ' 카테고리의 다른 글
[백준, BOJ 25757] 임스와 함께하는 미니게임 (java) (2) | 2024.10.22 |
---|---|
[백준, BOJ 4659] 비밀번호 발음하기 (java) (0) | 2024.10.22 |
[백준, BOJ 10431] 줄세우기 (java) (1) | 2024.10.17 |
[백준, BOJ 15823] 카드 팩 구매하기 (java) (5) | 2024.10.17 |
[백준, BOJ 16437] 양 구출 작전 (java) (1) | 2024.10.17 |