백준 12738 - 가장 긴 증가하는 부분 수열 3

백준 12738 - 가장 긴 증가하는 부분 수열 3

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

★ 풀이

가장 긴 증가하는 부분수열을 정해진 시간 내에 빠르게 구해야 한다. N 길이의 수열에서 이분탐색으로 가장 긴 증가하는 부분수열을 만들어나가면 O(n log n)으로 빠르게 구할 수 있다.

과정은 아래와 같다.

이분 탐색을 활용해서 위와 같은 방식으로 부분수열을 만들어 나가면 길이는 맞지만 내용물인 수열이 틀릴 수 있다. 하지만 위와 같은 방식으로 진행해야 계속 갱신이 일어나기 때문에 기존에 찾았던 부분수열의 길이보다 더 긴 부분 수열을 찾을 수 있고, 결국 문제에서 원하는 부분수열의 길이를 구하는데는 아무런 문제가 없기때문에 위와 같은 방식으로 진행해 주면 된다.

★ 소스 코드

import java.io.*; import java.util.*; // 좋은 스킬 흡수하기 public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); static int n; static int arr[]; static List ascList; public static void main(String[] args) throws IOException { n = Integer.parseInt(br.readLine()); arr = new int[n]; StringTokenizer st = new StringTokenizer(br.readLine()); for(int i = 0; i(); ascList.add(Integer.MIN_VALUE); for(int i = 0; i> 1; if(ascList.get(mid) >= num) { right = mid - 1; idx = mid; }else { left = mid + 1; } } ascList.set(idx, num); } } }

from http://sweet-smell.tistory.com/150 by ccl(A) rewrite - 2021-12-09 14:02:07