[백준14002번] 가장 긴 증가하는 부분 수열 4 / Python3

문제

수열 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

6
10 20 10 30 20 50

예제 출력 1

4
10 20 30 50

나의 풀이

가장 긴 증가하는 부분 수열 문제에서 이미 긴 증가하는 부분 수열의 길이를 구하는 법을 설명하였다. 여기서는 추가로 그 수열이 무엇인지를 알아내야한다. 이 방법은 dp에서 최댓값이 있는 인덱스 값부터 시작하여 거꾸로 탐색을 하면선 이 최댓값을 1씩 감소하며 일치하는 인덱스를 차례대로 구하면서 그때마다의 원래 수열에서의 해당 인덱스 값을 빈 리스트에 append를 해가며 저장을 한 뒤 마지막에 이 완성된 리스트를 거꾸로 출력을 해주면 된다.

예를들어 위의 dp가 완성이 되면 다음과 같다.

idx   0 1 2 3 4 5 
 dp   1 2 1 3 2 4

 이 경우에 최댓값이 4이고 그에 해당하는 idx는 5이므로 5와 4로 시작을 한다. 처음에 4와 4가 일치하니 리스트에 seq[5]를 append한다. 이후 idx를 1감소, cnt를 1감소시킨다. 그럼 [4,3]이 된다. dp[4] = 2로 일치하지 않으니 idx만 1만큼 감소시킨다. 그럼 [3,3]으로 dp[3] = 3으로 seq[3]을 리스트에 append하고 idx 1감소, cnt 1감소... 이렇게 쭉 끝까지 탐색을 한다.

코드

# 14002번 가장 긴 증가하는 부분 수열 4
import sys

# main
n = int(input())
seq = [int(x) for x in sys.stdin.readline().split()]

dp = [1 for _ in range(n)]

# 가장 긴 부분수열
for i in range(n):
    for j in range(i):
        if seq[j] < seq[i]:
            dp[i] = max(dp[i], dp[j]+1)

l_cnt = max(dp)
print(l_cnt)

idx = dp.index(l_cnt)
aSeq = []

# 긴 수열 찾아내기
while idx >= 0:
    if dp[idx] == l_cnt:
        aSeq.append(seq[idx])
        l_cnt -= 1
    idx -= 1

for num in aSeq[::-1]:
    print(num, end = ' ')
print()