[백준 12015] 알고리즘 102일차 : 가장 긴 증가하는 부분 수열 2

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

12015번: 가장 긴 증가하는 부분 수열 2

이분탐색 Java

(C++로 하려다가 xcode 맛가서 다시 java로 함..)

가장 긴 증가하는 부분 수열 2는 1과 달리 dp로 구하면 안되고 이분탐색으로 구해야한다.

N (1 ≤ N ≤ 1,000,000) 수열의 크기가 이렇기 때문에.

 

접근방법

도저히 모르겠어서 서치해서 공부했다.

좌 로직 우 이분탐색 lower bound 이해도(?)

핵심 개념은 이 두가지라고 생각하는데

증가하는 수열을 리스트로 선언해두고 배열을 하나씩 탐색하면서 수열의 가장 마지막 수(back)와 현재 배열의 한 수(value)를 비교한다.

back < value 이면 증가하는 부분 수열의 원소가 추가되는 것이므로 리스트에 value를 add한다.

back > value 이면 증가하는 부분 수열의 최대 길이를 유지하면서 계속 탐색하기 위해 value를 현재 상황에서 증가하는 부분수열의 lower_bound(value)위치의 값과 교체한다. 이 부분을 설명한 그림이 왼쪽 그림이다.

60자리에 50이 들어가면 기존의 10 60 70은 유지하면서 80이 들어왔을 때에 최대길이를 갱신할 수 있다.

이때는 사실상 50이 들어가있지만 실제 증가하는 부분 수열의 상태는 10 60 70 80이다.

50은 50이 증가하는 부분 수열의 포함되기 전까지 60을 대체하는 임시 숫자이다.

만약 뒤에 60 70 80 이라는 숫자가 더 추가되어 부분 수열이 그림과 같이 수정된다면

이때 50, 60은 임시가 아닌 50과 60이 포함된 수열이 증가하는 부분 수열이 된다.

 

그렇기 때문에 리스트의 끝값과 비교하여 크면 그대로 수열에 추가하고 아니라면 lowerbound자리에 임시로 들어가는 것이다(언젠가 내가 포함된 수열이 진짜 부분 수열이 될때를 대비하여)

 

소스코드

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;

public class B12015 {
    static ArrayList<Integer> al = new ArrayList<>();

    public static int lower_bound(int s, int e, int n){
        while(s < e){
            int mid = (s+e)/2;
            if(al.get(mid) >= n){
                e = mid;
            }else{
                s = mid + 1;
            }
        }
        return s;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        String s = br.readLine();
        String[] sarr = s.split(" ",n);
        int[] arr = Arrays.stream(sarr).mapToInt(a->Integer.parseInt(a)).toArray();

        al.add(0);
        for(int a : arr){
            if(al.get(al.size()-1) < a){
                al.add(a);
            }else{
                al.set(lower_bound(0,al.size()-1,a), a);
            }
        }
        al.remove(0); // 0제거
        bw.write(al.size()+"\n");

        bw.close();
        br.close();
    }
}