문제

가장 긴 증가하는 부분 수열 5
임의의 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 만든다.

• 수열 A = {10, 20, 10, 30, 20, 50} 일 때,
• {10, 20, 30}, {20, 10, 50}, {10, 20, 30, 50} 등이 모두 부분 수열이 될 수 있다.
  부분 수열 중, 원소들이 모두 증가하는 형태를 띄는 것을 증가 부분 수열이다.
  증가 부분 수열중 가장 긴 증가 부분 수열을 찾는 문제이다.

아이디어

핵심 아이디어

• LIS 문제는 DP, 이분탐색, 세그먼트 트리 등을 이용하여 길이를 구할 수 있다.
• LIS의 길이를 구하는 방법은 최장 증가 부분 수열 길이 구하기에 따로 정리해 두었다.
• LIS의 길이를 구하는 과정중에 원래 수열 A의 원소들이 LIS에서 어느 길이에 존재해야 하는지를 기록해 둔다.
• 위의 과정을 통해 얻은 위치를 통해 LIS를 찾아낸다.

풀이 아이디어

• 이분 탐색을 통해 LIS를 찾는다.
• 이분 탐색은 bisect 모듈을 이용하여 편하게 구할 수 있다.
• 이분 탐색을 통해 LIS의 길이를 구하는 과정에는 DP배열이 사용된다.
• DP배열의 idx는 length를 의미한다.
• A[i]의 원소가 LIS에 포함될 때, 길이가 얼마인지를 저장하는 loc배열을 사용한다.
• 위의 예시 A수열에서 idx = 4를 계산할 때
  - loc[4]의 값은 이분탐색을 통해 얻은 idx값을 저장하며 2가 저장될 것이다.
• loc을 역순으로 순회하며, 큰 값부터 차례로 ans에 누적시킨다.

풀이

import bisect

N = int(input())
A = list(map(int, input().split()))
DP = [] # idx : 길이, val : 해당 길이에 해당하는 가장 작은 값.
loc = [-1 for _ in range(N)]  # 해당 A[idx]의 값이 LIS의 몇 번째 순서에 위치하나?

for i, a in enumerate(A):
    idx = bisect.bisect_left(DP, a)
    loc[i] = idx
    if idx == len(DP):
        DP.append(a)
    else:
        DP[idx] = a

length = len(DP)  # LIS의 길이는 DP의 길이와 같다.
ans = [0] * length  
lis_idx = length

for i in range(len(loc) - 1, -1, -1):  # 역순으로 순회한다.
    if loc[i] == lis_idx - 1:  # 현재 loc[i]의 값이 현재 채워야할 lis_idx라면
        lis_idx -= 1
        ans[lis_idx] = A[i]  # 값을 채운다.

print(len(ans))
for a in ans:
    print(a,end=' ')