[백준] 14002번 (python 파이썬)

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

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

 

11053번과 비슷한 문제이다. 11053번 문제를 풀 수 있어야 이 문제도 풀 수 있다.

 

11053번 풀이 보러 가기 →

 

두 문제의 차이점으로는 11053번은 길이를 출력했지만, 이 문제는 길이 뿐 아니라 LIS 그 자체도 출력해야 한다.

11053번의 경우는 길이를 출력하기위해 길이정보를 메모이제이션을 했지만,

이 문제의 경우 LIS 그 자체를 출력해야 하기 때문에 LIS 정보를 메모이제이션 해야 한다.

 

arr_len = int(input())
arr = list(map(int,"10 20 10 30 20 50".split()))
LIS = [[item] for item in arr]

for i in range(arr_len):
  for j in range(i):
    if arr[i] > arr[j] and len(LIS[j]) + 1 > len(LIS[i]):
        LIS[i] = LIS[j] + [arr[i]]

longest_LIS = sorted(LIS,key=len)[-1]
print(len(longest_LIS))
print(*longest_LIS)