[백준 / 골드2] 12015 가장 긴 증가하는 부분 수열 2 (Java)

문제 보기

사용한 것

• 새로운 수가 들어갈 자리를 효율적으로 탐색하기 위한 lower-bound

풀이 방법

• 문제에서 주어진 것은 가장 긴 증가하는 부분 수열의 크기를 구하는 것이다.
• 따라서 정확한 수열을 구할 필요 없다.
• 따라서 다음과 같은 방법을 사용한다.
• 10, 20, 15, 30, 25, 50
  • 10
  • 10, 20
  • 10, 15(교체)
  • 10, 15, 30
  • 10, 15, 25(교체)
  • 10, 15, 25, 50
• 이와 같이 새로 들어올 수가 현재까지 가장 큰 수가 아니라면, 새로 들어올 수와 가장 차이가 나지 않는 큰 수와 교체한다.
• 교체해도 가장 중요한 크기를 구하는 데에는 영향을 주지 않는다.
• 예를 들어 10, 20 -> 10, 15로 교체한 경우 다음에 올 수에 따라
  • 16이 오는 경우 10, 15, 16
  • 14가 오는 경우 10, 15
• 즉, 교체만 되었고 수열의 크기의 변화가 없기 때문에 교체 전보다 수열의 크기가 커지지 않더라도 답은 같다.
• 교체한 수는 교체하기 전의 수보다 더 작기 때문에 모든 상황에서 교체 전의 수열보다 같거나 큰 값을 가진다.

코드

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        int idx = 1;
        while (st.hasMoreTokens()) {
            arr[idx++] = Integer.parseInt(st.nextToken());
        }

        int[] lis = new int[n + 1];
        int len = 1;
        lis[1] = arr[1];
        for (int i = 2; i <= n; i++) {
            if (arr[i] > lis[len]) {
                lis[++len] = arr[i];
            } else {
                int l = 1;
                int r = len;
                while (l < r) {
                    int m = (l + r) / 2;
                    if (arr[i] > lis[m]) {
                        l = m + 1;
                    } else {
                        r = m;
                    }
                }
                lis[l] = arr[i];
            }
        }

        System.out.println(len);
    }
}