문제

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

소스코드

import sys
input = sys.stdin.readline

if __name__ == "__main__":  
    n = int(input())
    arr = list(map(int,input().split()))
    dp = [1] * n
    max_value = 0
    result = []

    for i in range(n):
        for j in range(i):
            if arr[i] > arr[j]:
                dp[i] = max(dp[j]+1,dp[i])
                
    max_value = max(dp)
    print(max_value)
    idx = dp.index(max_value)

    while idx >= 0:
        if dp[idx] == max_value:
            result.append(arr[idx])
            max_value-=1
        idx-=1
    for num in result[::-1]:
        print(num,end = ' ')

설명

이전에 가장 긴 증가하는 부분 수열 문제에서 가장 긴 수열의 갯수를 구하였다. 여기에 추가로 그 수열이 무엇인지 찾아야한다. 우리가 구한 dp의 최대값 인덱스에서 거꾸로 탐색하면 수열을 찾을 수 있다.

내가 생각한 알고리즘을 다이어그램으로 표현해보았다.
idx를 줄이고 max_value를 줄인다(자기 자신을 제거하는거임) 근데 dp[idx]값이랑 max_value랑 다르면 idx만 줄여본다. 같으면 idx랑 max_value 값을 둘 다 하나씩 줄인다(자기 자신제거)

다이어그램에 따라서 값을 보면 아래 표와 같다.
마지막에 -1이 되면서 while문을 탈출한다.

후기

1. 처음에 max idx랑 max value를 dp에서 구할 때 for문을 이용해서 구했다;;; 그리고 나중에 max(dp)해서 max_value를 구하고 dp.index(max_value) 함수를 이용해서 값을 구했는데 사용하는 메모리용량이 같았다;; 그냥 나의 편의성을 위한 것;;

2. 항상 idx error 잘 체크하자ㅠ.ㅠ

3.역순 출력 for i in range([::-1]) 돈 폴겟 ~~!!!!