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

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

14002번: 가장 긴 증가하는 부분 수열 4

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

12738번: 가장 긴 증가하는 부분 수열 3

 

[문제]

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

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

 

[입력]

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

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,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해 출력하면 된다.

 

import bisect as bi

n = int(input())
a = list(map(int, input().split()))
INF = int(1e10)
tmp = [INF]*n
ans = [0]*n
for i, x in enumerate(a):
    idx = bi.bisect_left(tmp, x)
    tmp[idx] = x
    ans[i] = idx
max_ = bi.bisect_left(tmp, INF)
print(max_)
max_ -= 1
result = []
for i, k in enumerate(ans[::-1]):
    if k == max_:
        result.append(a[n-i-1])
        max_ -= 1
print(*result[::-1])

풀이 자체는 5와 동일한데, 복습해보았다. 3의 경우 결과 출력 부분을 제외하면 된다.