(백준 알고리즘 문제풀이) 14002번 가장 긴 증가하는 부분 수열 4

문제

 

문제 링크

 

문제 접근

• 이전에 가장 긴 증가하는 수열과 문제 유형이 비슷하지만 dp의 개수만이 아닌 dp의 최대 길이와 dp 내용물을 출력하는 것이다.
• dp를 우선 구해준 후 dp를 역배열한 후, dp의 최대값을 저장하고 1씩 줄여가면서 같은 값이 있을 때 새로운 리스트에 저장을 해준다.
• 그리고 리스트를 문자열로 출력해준다.

코드

import sys

N = int(sys.stdin.readline())

seq = list(map(int, sys.stdin.readline().split()))


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

count = max(dp)
result = list()
output = ""

for k in range(N-1, -1, -1):
    # print(dp[k])
    if dp[k] == count:
        count -= 1
        result.append(seq[k])

result.reverse()
for t in result:
    output += str(t) + " "

print(max(dp))
print(output)

느낀점

dp배열에 대한 활용을 역순으로 해주는 좋은 문제였다. 알고리즘 생각은 너무 어렵다..