[BOJ/Python] 9251번 LCS

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

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

최장 증가 부분순열 문제.
이때 최장 증가 부분순열이란

원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고,
그 길이가 최대인 부분 수열

이는 동적 계획법 문제로, dp 테이블을 만들어 풀이할 수 있다.

모든 원소가 1인 DP 테이블을 만들어주고, 조건에 따라 1을 더해주며 구한다.
이때 다음 LIS는 이전 LIS 값의 +1 한 것이다.

이 문제는 실제 증가 부분 순열을 출력하는 과정에서 '다음 LIS는 이전 LIS 값의 +1 한 것이다.' 를 역이용하여 풀이 가능하다.

최대 증가 부분 순열의 길이를 std로 두고, 반복문을 돌며 이를 하나씩 빼주며 dp 테이블에서 해당하는 값의 index를 역순으로 읽어온다. 

 

input = __import__('sys').stdin.readline

N = int(input())
li = list(map(int, input().split()))
dp = [1 for i in range(N)]

res = []
for i in range(N):
    for j in range(i):
        if li[i] > li[j]:
            dp[i] = max(dp[i], dp[j]+1)

print(max(dp))

std = max(dp)
for i in range(N-1, -1, -1):
    if dp[i] == std:
        res.append(li[i])
        std -= 1


for i in res[::-1]:
    print(i, end = " ")