[BOJ] 12016 가장 긴 증가하는 부분수열 - 이분탐색

www.acmicpc.net/problem/12015

12015번: 가장 긴 증가하는 부분 수열 2

알고리즘 생각을 깊게 해야한다. 구하는 것은 가장 긴 부분수열의 길이이므로 문자열 자체를 구할 필요가 없다.

리스트를 순회하면서 현재 최대값보다 크다면 삽입하여 최대값을 갱신하고, 만약 현재 최대값보다 작다면 현재 리스트에서 알맞은 자리를 찾아 교체한다. 문자열 자체는 중요하지 않기에 가능한 방법이다.

만약 정답 문자열을 구해야 한다면, 교체 당한 숫자를 저장해둬서 처리해야 한다.

import sys
 
 
def find(x):
    left, right = 1, len(stack)
    while left < right:
        mid = (left + right) // 2
        if stack[mid] > x:
            right = mid
        elif stack[mid] < x:
            left = mid + 1
        else:
            left = right = mid
    return right
 
 
N = int(sys.stdin.readline())
dp = list(map(int, sys.stdin.readline().split()))
stack = [0]
 
for i in dp:
    if stack[-1] < i:
        stack.append(i)
    else:
        stack[find(i)] = i
 
print(len(stack) - 1)