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

문제

문제 출처 : https://www.acmicpc.net/problem/12738

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

문제 풀이

접근

최장 부분 증가 수열 LIS 문제이다. 기존에 앞부분을 모두 다시 확인하는 O($N^2$) 방식은 시간 초과가 날 것이다.

풀이

기존에 앞부분을 전부 확인하는 대신 이분탐색으로 현재값이 들어갈 곳을 찾는다.

코드

from bisect import bisect_left

n = int(input())
a = list(map(int, input().split()))

dp = [1]
x = [a[0]]

for i in range(1, n):
    if a[i] > x[-1]:
        x.append(a[i])
        dp.append(dp[-1] + 1)
    else:
        idx = bisect_left(x, a[i])
        x[idx] = a[i]
print(dp[-1])

후기

현재값이 들어갈 곳을 이분탐색으로 찾아서 바꾼다는게 처음에는 “그럼 어떤 수가 먼저 나왔는지 알 수 없는거 아니야?” 하는 생각을 했다.
하지만 길이만 바뀌지 않으면 값이 변하지 않으므로 정답을 도출할 수 있다.