난이도 : 플레티넘 5
유형 : DP, 역추적
https://www.acmicpc.net/problem/14003

---

문제

가장 긴 증가하는 부분 순열 4 과 동일한 문제이다.
다른 점은 조건인데 4의 경우

A의 크기 N (1 ≤ N ≤ 1,000)
수열 A를 이루고 있는 Ai (1 ≤ Ai ≤ 1,000)

가 해당 범위에 있는 반면, 5의 경우

수열 A의 크기 N (1 ≤ N ≤ 1,000,000)
수열 A를 이루고 있는 Ai (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)
로 더욱 커지고, 음수도 포함되었기에 4의 방법인 이중 for문으로 풀면 시간초과가 난다.

그럼 어떻게 풀어야 할까?
O(NlogN) 의 시간 복잡도를 가지고 있는 이진(이분)탐색 으로 풀어야 한다.
이진 탐색과 이진탐색으로 푼 LIS 문제는 예전에 푼적이 있다.

bisect 모듈을 활용하면 이진탐색을 더 쉽게 구현할 수 있었다.
bisect 모듈은 삽입 위치 찾기와 정렬 유지하면서 삽입하기에 특화되어 있다.

주요함수 4개는 다음과 같다.

함수	기능	설명
bisect_left(a, x)	x값 이상이 처음 나오는 위치(인덱스) 반환	중복된 값이 있을 경우 가장 왼쪽 인덱스
bisect_right(a, x)	x값 초과가 처음 나오는 위치(인덱스) 반환	중복된 값이 있을 경우 가장 오른쪽 인덱스 + 1
insort_left(a, x)	bisect_left 위치에 x를 삽입	정렬 유지하면서 삽입
insort_right(a, x)	bisect_right 위치에 x를 삽입	정렬 유지하면서 삽입

해답 및 풀이

import sys, bisect
input = sys.stdin.readline

n = int(input()) # 원소 개수
arr = list(map(int,input().split())) # 원소들

LIS = [] # LIS 값을 임시로 저장할 리스트
pos = [0] * n # 각 원소가 LIS의 몇 번째 위치에 들어갔는 지 기록

for i in range(n):
    if not LIS or arr[i] > LIS[-1]:  # 원소가 LIS 리스트에 들어가있지 않고, LIS의 마지막 원소, 현재 LIS 의 가장 큰 원소값 보다 더 이 원소가 크다면
        LIS.append(arr[i])
        pos[i] = len(LIS)-1 # arr[i]가 추가된 위치. [1,2] 에 3이 추가되었다면 [1,2,3].length = 3, 3-1이니까 2로 2번째에서 추가되었다는 의미

    else: # arr[i] 값이 LIS의 마지막 값보다 작거나 같다면, 그냥 뒤에 붙이면 안되고, 적절한 위치를 찾아서 교체해야 한다.
        # bisect_left는 이진 탐색으로 arr[i]를 넣을 수 있는 가장 왼쪽 위치를 찾아준다.
        idx = bisect.bisect_left(LIS, arr[i]) # LIS에서 arr[i] 이상의 값이 처음 나오는 인덱스 값 반환
        LIS[idx] = arr[i] # arr[i] 값이 LIS의 idx
        pos[i] = idx # LIS에 idx에 뒤에 추가되었다는 의미
        
# 예시 
#arr = [3, 1, 2] , LIS = []
#i=0 → LIS=[3] -> LIS에 아무것도 없었으니 3 append
#i=1 → arr[i]=1 < LIS[-1]=3 → LIS의 마지막 요소보다 arr[i]값이 더 작으니 else문 실행
#idx = bisect_left(LIS,1) = 0 (arr[i]의 값인 1 이상의 값이 처음 나오는 위치는 인덱스 0 이니 idx는 0이 된다.) 
#LIS[idx]=arr[i] -> LIS[0] = 1 ( LIS의 idx번째 인덱스의 값 3이 1로 교체된다.) 

# LIS 길이
LIS_length = len(LIS)

# 역추적
answer = [] # 실제 LIS를 저장할 리스트
now = LIS_length - 1 # 지금 찾아야 할 LIS 위치 (맨끝부터)

for i in range(n-1, -1, -1): # n-1부터 -1 직전인 0까지, 1씩 감소하면서 진행
    if pos[i] == now: # 현재 원소가 우리가 원하는 LIS 위치라면,
        answer.append(arr[i]) # 복원할 LIS에 append
        now -= 1 # 다음에는 그 앞자리를 찾아야 함

        if now < 0: # 다 찾았으면 끝
            break

answer.reverse() # 뒤에서부터 찾았으니 뒤집음

print(LIS_length)
print(*answer)

역추적 흐름

arr = [3, 1, 2, 5, 4]
pos = [0, 0, 1, 2, 2]
최종 LIS 길이 = 3 → now = 2부터 시작

i (뒤에서부터)	arr[i]	pos[i]	now	매칭?	LIS에 추가?
4	4	2	2	✅ pos[i]==now	LIS=[4], now=1
3	5	2	1	❌	패스
2	2	1	1	✅ pos[i]==now	LIS=[4,2], now=0
1	1	0	0	✅ pos[i]==now	LIS=[4,2,1], now=-1 → 끝
0	3	0	…	이미 끝났으니 확인 X

---

이진 탐색과 bisect 를 복습할 수 있는 문제 였다. 역추적 배열 쓰는 것 더 익숙해져야 할 것 같다.