BOJ #12015 가장 긴 증가하는 부분 수열 2

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

문제 12015. 가장 긴 증가하는 부분 수열 2

문제 풀이

LIS(Longest Increasing Subarray) 문제란다. 처음 들어본 개념인데 동적 프로그래밍, 이진 탐색으로들 해결한다고 한다. 아마 다른 풀이 유형이 등장하면 또 막혀서 정리하러 올 듯 싶다.

이 문제는 부분 수열 자체가 아니라 길이를 요구한다. 따라서 부분 수열의 원소 추가 혹은 갱신 조건을 명확히 해야 한다. 증가하는 부분 수열이므로 부분 수열의 마지막 원소보다 더 큰 언소가 등장할 경우에만 원소를 추가하고 그 외엔 단순 갱신만 하여 길이를 늘리면 안된다.

• 부분 수열이 비었다면 추가하고 continue
• 부분 수열의 마지막 수보다 크다면 append
• 부분 수열의 마지막 수보다 작거나 같다면 값에 대한 부분 수열의 이진 탐색 lower bound에 해당하는 위치에 갱신한다. (마지막 값일 수도 있기 때문에 단순 skip은 곤란하다.)

python 코드

import sys
import bisect
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))
sol = []
for a in arr:
    if not sol:
        sol.append(a)
        continue
    if sol[-1] < a:
        sol.append(a)
    elif sol[-1] >= a:
        sol[bisect.bisect_left(sol, a)] = a
print(len(sol))