문제

풀이

  • 핵심
    • 긴 수열 길이 구하기
      • 순서 바꾸기로 가능
    • 긴 수열 구하기
      • 순서 바뀌어 다시 구해줘야함.
  • 실패
    • 순서가 바뀌는 걸 이해하지 못함.
      • 외워서 풀었다는 이야기
  • 코드
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

from bisect import bisect_left

n = int(input())
arr = list(map(int, input().split()))
idx_list = [0] * (n + 1)

longest_array = [arr[0]]

for i, val in enumerate(arr):
    if longest_array[-1] < val:
        longest_array.append(val)
        idx_list[i] = len(longest_array) - 1
    else:
        idx = bisect_left(longest_array, val)
        longest_array[idx] = val
        idx_list[i] = idx

print(len(longest_array))


ans = []
index = len(longest_array) - 1
for i in range(len(arr) - 1,-1,-1):
    if idx_list[i] == index:
        ans.append(arr[i])
        index -= 1

print(*ans[::-1])