BAEKJOON : 14002

No. 14002

1. Problem

2. Others' Solutions

• LIS 구하는 알고리즘 에 해당 부분 수열을 출력하는 기능 추가
• LIS 가 4라고 가정했을 때, 4는 3으로부터 도출된 것이고 3은 2로부터 도출 ... 따라서 -1 하면서 해당 요소를 result 리스트에 append

import sys

n = int(sys.stdin.readline().rstrip())   # n = 6 
seqeunce = [0] +list(map(int,sys.stdin.readline().rstrip().split()))   
dp = [1] * (n+1)
result = []

for i in range(1,n+1): 
    for j in range(1,i): 
        if seqeunce[j] < seqeunce[i]:
            dp[i] = max(dp[i], dp[j] + 1)
        
temp = max(dp)

for i in range(n,0,-1):
    if dp[i] == temp:
        result.append(seqeunce[i])
        temp -= 1

print(max(dp))
print(' '.join(map(str,sorted(result))))

3. Learned

• 문제를 가시적으로 표현하여 알고리즘을 생각해보자