아이디어

• 백준 11053 '가장 긴 증가하는 부분 수열'에서 사용할 수 있는 알고리즘, $i$에 대해 $1\le j < i$ 중 $A_j < A_i$인 것들의 최대 memo[j] 값을 선형 탐색하는 방법은 $O(N^2)$의 시간복잡도를 갖는다.
  • 그러나 이 두 문제에서는 $N \le 1\ 000\ 000$이므로 더 효율적인 알고리즘이 필요하다.
• memo[k]를 '길이가 $k$인 증가 부분 수열의 마지막 자릿값'이라고 정의하자.
  • 마지막 자릿값이 작은 경우는 그보다 마지막 자릿값이 클 경우를 내포한다.
  • 이때 memo[]는 증가 수열의 형태를 띌 것이다.
    • 길이가 $k$일 때는 $k+1$일 때보다 항상 마지막 자릿값이 작거나 같으므로...
• 현재 구한 최대의 $k$ 이하 범위에서 memo[i] 값의 upper bound 위치를 찾는다.
  • 이진탐색을 이용한다.
  • 만약 그 위치가 $k+1$라면 증가 수열의 길이가 늘어난 것이다. k를 증가시킨다.
  • 해당 위치의 memo 값을 덮어쓴다. 이 값은 항상 더 작거나 같을 것이다.
• Java라면 Arrays.binarySearch(arr, start, end, key) 메소드의 리턴값의 정의를 이용하면 쉽게 구현할 수 있다.

코드

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

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer tk = null;

	static int N, ans;
	static int[] A, C;
	static int INF = Integer.MAX_VALUE / 2;
	
	public static void main(String[] args) throws Exception {
		N = Integer.parseInt(rd.readLine());
		
		tk = new StringTokenizer(rd.readLine());
		A = new int[N];
		for (int i=0; i<N; i++) {
			A[i] = Integer.parseInt(tk.nextToken());
		}
		
		C = new int[N+1];
		Arrays.fill(C, INF);
		for (int i=0; i<N; i++) {
			int ip = -(Arrays.binarySearch(C, 0, ans, A[i]) + 1);
			if (ip < 0) continue; // upper bound의 값이 일치한다면 아무 것도 안 한다.
			C[ip] = A[i];
			if (ip == ans) ans++;
		}
		
		System.out.println(ans);
	}
}

메모리 및 시간

• 메모리: 95972 KB
• 시간: 536 ms

리뷰

• 이런 풀이는 대체 어떻게 생각해내는 걸까
• 문제 '~~ 2'를 풀 수 있지만 '~~ 3'을 풀 수 없는 다른 알고리즘이 존재하는 걸까?