[코딩 테스트 연습(파이썬/Python)] 백준 14003번 _ 가장 긴 증가하는 부분 수열 5

https://www.acmicpc.net/problem/14003

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) 충분히 큰 값으로 초기화한 길이 N의 배열을 두고, 수열의 모든 수에 대해 bisect_left를 통해 증가수열이 되도록 하는 위치에 해당 수를 업데이트한다.

2) 이때 초기화한 INF값을 제외하고 만들어진 배열의 길이가 LIS의 길이이다.

3) 1)의 과정을 수행할 때, 수열의 각 수로 배열의 특정 위치를 업데이트 할 때마다, 업데이트 하는 위치 정보를 ans 배열에 따로 저장한다.

4) 이렇게 저장한 ans 배열의 경우 ans[i] = (i번째 위치까지의 LIS의 길이 -1)을 의미하며, 이때 LIS의 마지막 수는 a[i]이다.

5) 4)와 2)에서 구한 LIS의 길이를 이용해 역으로 LIS의 숫자 구성을 추적할 수 있다. 예를 들어 LIS의 길이가 4이면 ans의 배열의 뒤에서부터 3,2,1,0의 값을 갖는 위치 i를 찾아내어 a[i] 값들을 모은 뒤, 이를 reverse해 출력하면 된다.

 

# LIS 5
import bisect as bi
n = int(input())
a = list(map(int, input().split()))

ans = [0]*n
INF = int(1e10)
inc_arr = [INF]*n
for i, x in enumerate(a):
    idx = bi.bisect_left(inc_arr,x)
    inc_arr[idx] = x
    ans[i] = idx

result = []
end = max(ans)
for i in range(n-1,-1,-1):
    if ans[i]== end:
        result.append(a[i])
        end-=1
print(len(result))
print(*result[::-1], sep=' ')

좀 어려웠다,, 비슷한 다른 문제들로 복습해봐야겠다.