BOJ 12015 가장 긴 증가하는 부분 수열 2, BOJ 12738 가장 긴 증가하는 부분 수열 3, BOJ 14002 가장 긴 증가하는 부분 수열 4, BOJ 14003 가장 긴 증가하는 부분 수열 5

https://www.acmicpc.net/problem/12015
시간 1초, 메모리 512MB

https://www.acmicpc.net/problem/12738
시간 3초, 메모리 512MB

https://www.acmicpc.net/problem/14002
시간 1초, 메모리 256MB

https://www.acmicpc.net/problem/14003
시간 3초, 메모리 512MB

input :

• N (1 ≤ N ≤ 1,000,000)
• Ai (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)

output :

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

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

조건 :

• 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램

---

DP 또는 이분탐색, 세그 트리를 사용해서 풀어야 하는 문제인데 위의 dp의 경우 시간 복잡도가 크게 소요되어서 이분탐색을 공부하는 방식을 사용했다.

현재 입력된 수열에 대해서 이 수열의 원소를 부분 수열의 어느 위치에 넣을 수 있는 가를 판단하는 방식을 사용한다.

10 20 10 30 20 50
의 예시에서

현재 부분 수열의 가장 뒤에 위치하는 값보다 큰 값이라면 부분수열의 길이를 늘려주지만 그렇지 않은 경우에는 자기 보다 작은 위치를 찾는다.

이분탐색의 방식이 좀 이상하긴 한데 이 때 얻는 결과 값은 문제가 원하는 부분 수열이 아니다. 그래서 다시 위치를 찾아야 하는데 이를 위해 인덱스를 저장할 배열이 필요하다.

인덱스의 경우 1부터 시작하게 해서
1 2 1 3 2 4
가 될 텐데 이 때 뒤에서 부터 가장 큰 값을 찾도록 해서 찾아간 다면
10 20 30 50 을 가지고 올 수 있게 된다.

import sys
from bisect import bisect_left

n = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))
temp, idxs = [data[0]], [0] * n
idxs[0] = 1

for i in range(1, n):
    if temp[-1] < data[i]:
        temp.append(data[i])
        idxs[i] = len(temp)
    else:
        idx = bisect_left(temp, data[i])
        temp[idx] = data[i]
        idxs[i] = idx + 1

ans, j = [], len(temp)
for i in range(len(idxs) - 1, -1, -1):
    if idxs[i] == j:
        ans.append(data[i])
        j -= 1

    if j < 1:
        break

print(len(ans))
print(*ans[::-1])