백준 14003번 LIS

서론

14003번: 가장 긴 증가하는 부분 수열 5

LIS에서의 역추적 문제입니다. LIS(Longest Increasing Sequence)문제자체를 많이 풀어보았고 최근에 최단 경로를 역추적하는 문제도 많이 풀고 있었기 때문에 LIS에도 prev리스트를 선언해서 풀면 역추적까지 되겠다고 생각했지만 못 풀었습니다.

시간제한 있는 LIS였기 때문에 단순하게 O(n^2)을 가지는 DP로 못 풀고 O(nlogn)을 가지는 이분탐색을 활용하는 방법으로 풀어야 했습니다. 이것 때문에 지금까지 역추적을 풀 때 사용한 이전 정점을 담는 리스트를 선언하는 게 어려웠고 다른 방법으로 구현해서 풀었습니다.

제한 조건

• 시간제한 - 3초

시간제한은 3초입니다. 일반적인 컴퓨터로 1초에 1억 번 연산한다는 기준을 가지고 풉니다. 3초여서 꽤 길어 보이지만 N이 1,000,000이기 때문에 n^2로 풀면 안 됩니다. nlogn으로 풀어야 합니다.

• 메모리 제한 - 512MB

메모리 제한은 512MB입니다. 선언할 부분이 1,000,000개의 데이터 정도인데 파이썬 기본 정수형 타입이 28byte이니 28MB이고 경로를 역추적하기 위한 리스트가 필요하니 28MB 더 선언한다고 해도 메모리는 충분합니다. 또 문제를 풀기 위해서 따로 자료구조를 가지는 게 아니니까 메모리는 걱정 없습니다.

LIS

LIS nlogn의 방법으로 풀어야 합니다. 정석적인 nlogn으로 풀었을 때 나오는 리스트는 LIS의 원소들을 담고 있는 게 아니기 때문에 역추적하기 위해서 다른 방법을 사용하여야 합니다.

path를 N 크기 만큼 선언하고 num_list[인덱스]가 LIS를 구성할 때 몇 번째 숫자인지를 넣었습니다. 그리고 여기서 중요한 점이 LIS에서 nlogn을 사용해서 구현하면 뒤로 갈수록 앞의 LIS 구성 원소를 덮어쓰기 때문에 역추적할 때도 이를 생각하고 뒤에서부터 해주어야 합니다. 코드를 보면 더 이해하기 쉬울 것 같습니다.

from bisect import bisect_left
import sys
input = sys.stdin.readline

N = int(input())
num_list = list(map(int, input().split()))
tmp = [-sys.maxsize]
path = [0]*N

for i in range(N):
    if num_list[i] > tmp[-1]:
        tmp.append(num_list[i])
        # num_list[i]가 LIS에서 몇번째로 등장하는지 path에 넣음.
        path[i] = len(tmp)-1
    else:
        idx = bisect_left(tmp, num_list[i])
        tmp[idx] = num_list[i]
        # num_list[i]가 LIS에서 몇번째로 등장하는지 path에 넣음.
        path[i] = idx

lentmp = len(tmp)-1
print(lentmp)
path = []

# 뒤에서 부터 확인합니다.
for i in range(N-1, -1, -1):
    if path[i] == lentmp:
        path.append(num_list[i])
        lentmp -= 1
print(*reversed(path))

생각