[Python] 14002 - 가장 긴 증가하는 부분 수열 4 (골드4)

1. 문제 설명

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

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

 

[참고]

[Python] 11053 - 가장 긴 증가하는 부분 수열 (실버2)

[Python] 12015 - 가장 긴 증가하는 부분 수열 2 (골드2)

[Python] 12738 - 가장 긴 증가하는 부분 수열 3 (골드2)

 

---

2. 아이디어

lis 알고리즘을 쓰면 틀린다.

이 문제는 길이와 증가 부분 수열까지 출력해야 하므로 11053 문제 처럼 DP로 해결해야 한다.

 

---

3. 코드

import sys

input = sys.stdin.readline

def solution():
    n = int(input())
    a = list(map(int, input().split()))
    cache = [0]*n
    result = []

    for i in range(n):
        for j in range(i):
            if a[i] > a[j] and cache[i] < cache[j]:
                cache[i] = cache[j]
        cache[i] += 1
    print(max(cache))

    order = max(cache)
    for i in range(n-1, -1, -1):
        if cache[i] == order:
            result.append(a[i])
            order -= 1
    result.reverse()

    for i in result:
        print(i, end=' ')

solution()