[Java] 백준 14003번 가장 긴 증가하는 부분 수열 5

다이나믹 프로그래밍, 이분 매칭 문제입니다.

https://j3sung.tistory.com/945

[Java] 백준 12015번 가장 긴 증가하는 부분 수열 2

https://j3sung.tistory.com/947

[Java] 백준 14002번 가장 긴 증가하는 부분 수열 4

위 두 문제를 합친 문제입니다.

DP와 이분매칭을 활용해서 LIS의 길이를 찾습니다. (LIS2문제와 동일하게)
그리고 위의 과정에서 값이 해당 인덱스로 들어갈 때 그 인덱스의 값을 저장해줍니다.
저장된 인덱스를 뒤에서 부터 탐색하여 수열을 찾아냈습니다. (LIS4문제와 동일하게)

찾아낸 길이와 수열을 출력해주었습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	static int n;
	static int cnt;
	static int[] arr;
	static int[] ansArr;
	static ArrayList<Integer> dp;
	static ArrayList<Integer> record;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = null;
		
		n = Integer.parseInt(br.readLine());
		arr = new int[n];
		dp = new ArrayList<>();
		record = new ArrayList<>();

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; ++i) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		for (int i = 0; i < n; ++i) {
			if (dp.size() == 0 || dp.get(dp.size() - 1) < arr[i]) {
				dp.add(arr[i]);
				record.add(dp.size() - 1);
			} else {
				int left = 0;
				int right = dp.size() - 1;
				while (left < right) {
					int mid = (left + right) >> 1;
					if(dp.get(mid) >= arr[i]) {
						right = mid;
					} else {
						left = mid + 1;
					}
				}
				dp.set(right, arr[i]);
				record.add(right);
			}
		}

		cnt = dp.size() - 1;
		ansArr = new int[cnt + 1];
		for(int i=n-1; i>=0; --i) {
			if(record.get(i) == cnt) {
				ansArr[cnt] = arr[i];
				--cnt;
			}
		}
		
		bw.write(dp.size() + "\n");
		for(int i=0; i<ansArr.length; ++i) {
			bw.write(ansArr[i] + " ");
		}
		bw.write("\n");
		bw.close();
	}
}

d