[백준/14002/파이썬] 가장 긴 증가하는 부분 수열 4

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

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

Problem

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

SOL

N이 N^2으로 충분히 해결이 가능하기 때문에, DP방식으로 오랜만에 구현을 해주었다.

DP 방식으로 구현해주면, Lis의 길이가 최대인 곳의 index부터 1개씩 줄여나가면서, LIS를 직접 구하는 방법도 가능하다.

import sys
input= sys.stdin.readline
N=int(input().rstrip())
seq=list(map(int,input().split()))
DP=[1]*N

for i in range(N):
    for j in range(i):
        if seq[j]<seq[i]:
            DP[i]=max(DP[i],DP[j]+1)

Lis_len=max(DP)
print(max(DP))

Lis_seq=[]
idx=DP.index(Lis_len)
while idx>=0:
    if DP[idx] ==Lis_len:
        Lis_seq.append(seq[idx])
        Lis_len-=1
    idx-=1

for num in Lis_seq[::-1]:
    print(num,end=" ")