BOJ-14003 - Python

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열(LIS)를 구하는 문제. 해당 LIS의 길이와 수열을 공백으로 나누어 출력하는 문제. 이분탐색을 이용하여 LIS의 길이를 저장했으며 배열에 각 인덱스의 LIS를 저장하여 해당 값을 비교, 감소하여 수열의 구성요소를 판별하여 풀었다. 자세한 풀이는 주석 참고

from bisect import bisect_left

n = int(input())
l = list(map(int, input().split()))
dp = [0 for _ in range(n)]
cmp = [] # 이분탐색을 위해
maxVal = 0 # 최대값

for i in range(n):
    if i == 0: # 첫 번째일 때 추가만
        cmp.append(l[i])
        continue

    if cmp[-1] < l[i]: # 저장된 값과 비교하여 클 시
        cmp.append(l[i])
        dp[i] = len(cmp) -1
        maxVal = dp[i]
    else:
        # 작을 시 어느 위치의 값에 해당하는 지
        dp[i] = bisect_left(cmp, l[i])
        cmp[dp[i]] = l[i]

# 최대 길이 출력
print(maxVal + 1)

# 인덱스별 길이를 기준으로 수열 저장
res = []
for i in range(n-1, -1, -1):
    if dp[i] == maxVal:
        res.append(l[i])
        maxVal -= 1
res.reverse()

print(*res)