[Python] 백준 - 14003 가장 긴 증가하는 부분 수열 5

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)

 

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

둘째 줄에는 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력한다.

 

 

문제해결방법 - (구글링 참조)

 

1. 아 이진탐색으로 푸는 방법은 14002문제 다음에 또 있었구나.

2. 이거 혼자 떠올리면 진짜 천재아닌가?

 

주어진 리스트를 d 라고 할 때, 문제의 예제에 끝에 15를 추가했다. (res와 dp에 저장된 순서대로의 원소가 다른 예)

 

res = [d[0]] < 미리 저장. for문에서 처리해도 된다.

 

1) for i in range(1, n): 을 돌 때, 각 변수들의 변화

 

◈ res의 빨간 색 밑줄 표시는 이진탐색으로 찾은 d[i]가 들어갈 위치이다.

i	1	2	3	4	5	6	7
d[i]	10	20	10	40	20	50	15
res	[10]	[10, 20]	[10, 20]	[10, 20, 40]	[10, 20, 40]	[10, 20, 40, 50]	[10, 15, 40, 50]
dp	[1, 10]	[1, 10] [2, 20]	[1, 10] [2, 20] [1, 10]	[1, 10] [2, 20] [1, 10] [3, 40]	[1, 10] [2, 20] [1, 10] [3, 40] [2, 20]	[1, 10] [2, 20] [1, 10] [3, 40] [2, 20] [4, 50]	[1, 10] [2, 20] [1, 10] [3, 40] [2, 20] [4, 50] [2, 15]

 

 

- d[i]가 기존의 마지막 값(res[-1])보다 작을 시, 이진 탐색 함수에서 이 d[i]가 들어갈 인덱스를 찾는다.

 

a. target이 mid와 일치하면 mid값 출력. 그 후 res에는 변동이 없고, dp에는 [인덱스, target]이 추가된다.

b. target이 mid와 같지 않을 때, l 출력. l이 mid+1 되면서 끝나든, r이 mid-1 되면서 끝나든 l을 출력하면 target값보다 작은 원소의 인덱스 다음으로 설정된다. 

 

-> 처음에 코드를 작성할 때, 그냥 res의 원소가 증가하는 수열로 쌓이는 것 아닌가 헷갈릴 수도 있는데, 위를 보면 res에 15가 순서도 아닌데, 반영되어 있는 것을 알 수 있다. (반례인 셈.)

 

-> dp에서 인덱스번호로 역추적하여 출력하자.

 

 

import sys
from collections import deque
input = sys.stdin.readline

n = int(input())
d = list(map(int, input().split()))
dp = [[0, 0] for _ in range(n)]
res = []
ans = []
dp[0] = [1, d[0]]

def binary(arr, k, l, r):
	if l > r:
		return l
	mid = (l+r)//2
	if arr[mid] == k:
		return mid
	elif arr[mid] < k:
		return binary(arr, k, mid+1, r)
	else:
		return binary(arr, k, l, mid-1)

for i in range(n):
	if not res:
		res.append(d[i])
	if res[-1] < d[i]:
		res.append(d[i])
		dp[i] = [len(res), d[i]]
	else:
		idx = binary(res, d[i], 0, len(res)-1)
		res[idx] = d[i]
		dp[i] = [idx+1, d[i]]
print(len(res))
rdx = len(res)
for i in range(n-1, -1, -1):
	if dp[i][0] == rdx:
		ans.append(dp[i][1])
		rdx -= 1
print(*ans[::-1])