Baekjoon 14003. 가장 긴 증가하는 부분 수열 5 / Python

https://www.acmicpc.net/problem/14003

알고리즘 설명

1. 이진 탐색을 활용한 LIS 찾기:
   • LIS를 효율적으로 찾기 위해 이진 탐색을 사용합니다.
   • LIS 배열 Lis를 유지하며, 새로운 원소가 들어올 때 적절한 위치에 삽입합니다.
   • Lis 배열은 항상 정렬된 상태로 유지됩니다.
2. LIS 길이 저장:
   • 각 원소에 대해 LIS 배열에 추가할 때 그 위치와 원소를 기록하는 dp 배열을 유지합니다.
   • 이는 나중에 실제 LIS 수열을 복원하는 데 사용됩니다.
3. 이진 탐색 구현:
   • binary(goal) 함수는 goal 값을 LIS 배열에서 찾고, 적절한 위치를 반환합니다.
4. LIS 복원:
   • dp 배열을 역순으로 탐색하여 실제 LIS 수열을 복원합니다.
   • LIS 길이에 해당하는 값들을 뒤에서부터 찾습니다.

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

# LIS 배열 
Lis = [arr[0]]

# dp 배열 (index, value)
dp = [(0, arr[0])]

def binary(goal):
    # 이진 탐색 함수: goal 값을 LIS에서 찾고 적절한 위치 반환
    s = 0
    e = len(Lis) - 1
    while s <= e:
        m = (s + e) // 2
        if Lis[m] == goal:
            return m
        elif Lis[m] < goal:
            s = m + 1
        else:
            e = m - 1
    return s

# LIS 및 dp 배열 업데이트
for i in range(1, n):
    if arr[i] > Lis[-1]:
        Lis.append(arr[i])
        dp.append((len(Lis) - 1, arr[i]))
    else:
        idx = binary(arr[i])
        Lis[idx] = arr[i]
        dp.append((idx, arr[i]))

# LIS 길이 출력
print(len(Lis))

# 실제 LIS 수열 복원
tmp = len(Lis) - 1
res = []
for i in range(len(dp) - 1, -1, -1):
    if dp[i][0] == tmp:
        res.append(dp[i][1])
        tmp -= 1

# LIS 수열 출력
print(*res[::-1])