[Java] BOJ12015_가장 긴 증가하는 부분 수열 2

www.acmicpc.net/problem/12015

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

---

최장 증가 부분 수열 문제이다. 하지만 N의 범위가 크기 때문에 단순 이중 반복문으로는 해결이 되지 않는다.

이 경우에는 이분 탐색을 사용해야 한다.

 

dp 배열에는 최장 증가 부분 수열을 이루는 요소가 담긴다. 하지만 주의할 점은 이 요소들이 항상 최장 부분 수열이라는 것을 보장하지는 않는다. 그저 개수만 맞을 뿐이다. 정확한 요소를 골라내기 위해서는 다른 방법을 사용해야 한다.

하지만 이 문제는 개수만 구하면 되기 때문에 그 부분은 신경 쓰지 않아도 된다.

 

dp[index] 부분에는 가장 큰 수가 담겨있다. 따라서 그보다 큰 값이 들어오면 그 수 다음에 바로 삽입해준다.

그보다 작은 값이 들어오면 이분 탐색을 통해 그 수가 들어가야 할 위치를 찾고 그 위치에 있던 수와 교환이 된다. 따라서 이 때는 index가 증가하지 않는다.

같은 값은 고려할 필요가 없다.

 

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

//LIS 이분탐색
public class Main {

	static int[] arr;
	static int[] dp;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		arr = new int[N];
		dp = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		int index = 0;
		dp[0] = arr[0];
		for (int i = 1; i < N; i++) {
			if(arr[i] > dp[index]) dp[++index] = arr[i];
			else if(arr[i] < dp[index]) binarySearch(0, index, arr[i]);
		}
		
		System.out.println(index+1);
	}
	
	public static void binarySearch(int start, int end, int data) {
		int mid = (start+end)/2;
		if(start >= end) {
			if(dp[mid] < data) dp[mid+1] = data;
			else dp[mid] = data;
			return;
		}
		
		if(dp[mid] > data) {
			binarySearch(start, mid-1, data);
		} else if(dp[mid] < data) {
			binarySearch(mid+1, end, data);
		} else {
			return;
		}
	}
	
}

 

 

[참고]

최장 증가 부분 수열에 대해 정리가 잘 되어있는 블로그다.

jason9319.tistory.com/113

[최장 증가 수열] LIS(Longest Increasing Subsequence)