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

문제 링크

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

 

문제 풀이

• 최대 길이를 구하려면 현재 위치의 값에서 앞에 작은 값들이 얼마나 있는지를 계산하면 된다.
• 수열 10, 20, 10, 30, 20, 50이 있다고 가정한다. 
  • 첫 번째 위치인 10은 자신 하나므로 최대 길이가 1이 되고, 두 번째 위치인 20은 자신과 그 앞의 숫자로 최대 길이가 2가 된다.
  • 세 번째 위치인 10은 앞의 두 숫자가 모두 작지 않으므로 최대 길이가 1이 된다.
  • 이를 점화식으로 표현하면 arr[j] < arr[i] (j < i), dp[i] = max(dp[i], dp[j] + 1) 가 된다.
  • 점화식을 통해서 구한 dp  배열의 최댓값이 최대 길이가 된다.
• 최대 길이가 될 때의 수열을 구하기 위해서는 dp 배열 맨 뒤에서 큰 값부터 찾아야 한다. (앞에서 부터 작은 값을 찾는 경우의 반례: 999, 1000, 1, 2, 3)
• 수열을 구한 후 이를 뒤집어서 출력해야 한다.

 

전체 코드

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))

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

res = []
k = max(dp)
for i in range(n-1, -1, -1):
    if dp[i] == k:
        if k == max(dp):
            res.append(arr[i])
        else:
            if arr[i] < res[-1]:
                res.append(arr[i])
        k -= 1

print(max(dp))
print(" ".join(map(str, res[::-1])))