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

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

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

 

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

Logic

1. 최장 증가 수열을 구하기 위한 LIS 알고리즘을 사용한다.
2. 최장 증가 수열의 크기를 출력한다.

 

이 문제의 경우 현재 값에서 앞선 수들을 비교하는 일반 DP로는 O(n^2)이므로 시간 초과가 발생한다. 그래서 이분 탐색을 이용한(Lower Bound) LIS알고리즘(Longest Increasing Subsequence Algorithm)을 사용하여(O(NlogN)) 문제를 해결해야 한다.

 

우선, LIS 알고리즘의 정의를 보자면 길이 k의 증가 수열에 대하여 길이 k자리 위치에 올 수 있는 가능한 값 중 가장 작은 값을 구하여 수열의 길이를 구한다고 할 수 있다. 이 과정에서 이진 검색이 이용된다.

그렇다면 LIS가 수행되는 과정을 보자.

 

위와 같은 배열이 있다고 했을 때 LIS 알고리즘을 적용하여 가장 긴 증가하는 부분 수열을 구해보자.

 

Arr[1] 요소는 DP배열이 비어 있으므로 1번째에 위치한다.

 

Arr[2] 요소 2를 보면 기존 DP배열 [3]에서 3보다 앞쪽에 위치할 수 있으므로 기존 3의 값에 2를 넣어준다.

 

Arr[3] 요소 6은 기존 DP배열 [2]에서 2보다 뒤쪽에 위치할 수 있으므로 기존 배열의 뒤에 추가한다.

 

Arr[4] 요소 4는 기존 DP배열 [2, 6]에서 들어갈 수 있는 위치를 보면 2와 6 사이에 들어갈 수 있지만 위에서 언급했듯 LIS는 k자리 위치에 올 수 있는 가능한 값 중 가장 작은 값이다. 그러므로 6을 4로 치환한다.

 

Arr[5] 요소 5는 [2, 4]에서 4 뒤에 올 수 있으므로 기존 배열 뒤에 추가한다.

 

마지막 Arr[6] 요소 1은 [2, 4, 5] 배열에서 2의 앞에 위치할 수 있으므로 2를 1로 치환한다.

 

LIS 수행이 끝나고 구해진 배열은 [1, 4, 5]로 길이 3짜리 수열이 만들어 졌다.

그러므로 가장 긴 증가하는 부분 수열의 길이는 3이 된다.

 

그런데 이런 의문이 생길 것이다, 1이 맨 뒤에 있는데 왜 부분 수열에서 맨 앞에 위치하지?? 라는 의문이 생길텐데 LIS 알고리즘은 최장 증가 수열의 크기만 구할 수 있을 뿐 실제의 최장 증가 수열의 값을 알지는 못한다. 실제 최장 증가 수열을 구하기 위해선 LIS를 구할 때 해당 숫자의 Index를 따로 저장하여 관리하면 구할 수 있다.

 

JAVA에선 배열의 이분 탐색으로 binarySearch 함수를 제공한다.

binarySearch 함수는 정렬된 배열에서 찾는 값이 있으면 해당 Index를 반환하고, 찾는 값이 없으면 해당 값이 들어갈 수 있는 위치의 음수 값에서 1을 뺀 값을 반환한다. 1을 빼주는 이유는 0번째 Index 때문인데 자세한건 직접 찾아보자.

 

CODE

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

/**
 * 백준 12015. 가장 긴 증가하는 부분 수열 2 - 골드 2
 * @category DP
 */
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];
		int[] LIS = new int[N];
		
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		int size = 0;
		for (int i = 0; i < N; i++) {
			int pos = Arrays.binarySearch(LIS, 0, size, arr[i]);
			if(pos >= 0) continue;
			
			int iPos = Math.abs(pos) - 1;
			LIS[iPos] = arr[i];
			
			if(iPos == size) size++;
		}
		
		System.out.println(size);
	}
}