주어진 배열 : 2, 5, 3, 7, 11, 8, 10, 13, 6
-----------------------------
아무것도 없으므로 2 입력
2
-----------------------------
5 > 2 이므로 5입력
2, 5
-----------------------------
3 < 5 이므로 배열에서 3보다 큰것중에 가장 작은것에 입력
2, 3
-----------------------------
7 > 3 이므로 7입력
2, 3, 7
-----------------------------
11 > 7 이므로 11입력
2, 3, 7, 11
-----------------------------
8 < 11 이므로 배열에서 8보다 큰것중에 가장 작은것에 입력
2, 3, 7, 8
-----------------------------
10 > 8 이므로 10입력
2, 3, 7, 8, 10
-----------------------------
13 > 8
2, 3, 7, 8, 10, 13
-----------------------------
6 < 13 이므로 6보다 큰것중 가장 작은것에 입력
2, 3, 6, 8, 10, 13
import java.util.Arrays;
import java.util.Scanner;
public class test11053_dp {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] arr = new int[sc.nextInt()];
for (int i = 0; i < arr.length; i++)
arr[i] = sc.nextInt();
// 부분수열을 만들어서 넣어줄 배열
int[] tailTable = new int[arr.length];
tailTable[0] = arr[0]; // 빈 배열에 첫번째 요소 추가
int tailIdx = 0; // 꼬리의 index
for(int i=1; i<arr.length; i++) {
// 넣을 요소가 꼬리요소 보다 크다면 삽입
if(arr[i] > tailTable[tailIdx]) {
tailTable[++tailIdx] = arr[i];
}
// 넣을 요소가 꼬리요소 보다 작으면, 요소들중에서 자기보다 큰것중 가장 작은것과 교환
else{
int insertIdx = Arrays.binarySearch(tailTable, 0, tailIdx, arr[i]);
// 0보다 크거나 같을 경우는, 요소가 이미 있을 경우이다.
insertIdx = insertIdx >= 0 ? insertIdx : -(insertIdx) -1;
tailTable[insertIdx] = arr[i];
}
}
for(int t:tailTable)
System.out.print(t+" ");
System.out.println(tailIdx+1);
}
}
