[백준] 12738. 가장 긴 증가하는 부분 수열 3

문제 링크

[백준] 12738. 가장 긴 증가하는 부분 수열 3

풀이 과정

수열의 요소 값의 범위가 다르다는 것을 제외하곤 [백준] 12015. 가장 긴 증가하는 부분 수열 2와 같아, 동일한 코드를 제출해서 풀었습니다.

코드

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

public class Main {
    static int[] arr;
    static int[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        dp = new int[N];
        dp[0] = arr[0];
        int idx = 0;

        for (int i = 1; i < N; i++) {
            if (arr[i] > dp[idx]) {
                dp[++idx] = arr[i];
            } else {
                int targetIdx = binarySearch(idx, arr[i]);
                dp[targetIdx] = arr[i];
            }
        }

        System.out.println(idx + 1);
    }

    static int binarySearch(int high, int target) {
        int low = 0;

        while (low <= high) {
            int mid = (low + high) / 2;

            if (dp[mid] < target) low = mid + 1;
            else high = mid - 1;
        }

        return low;
    }
}