[python] 동적프로그래밍_백준 14002번

이희진·2023년 4월 11일
0

백준 14002번 - 가장 긴 증가하는 부분 수열 4

이 문제는 계속 반복적으로 나오는 가장 긴 증가하는 수열 찾기 문제이다. 동적 프로그래밍 방식으로 풀어보자.

풀이

먼저 앞에서부터 각 위치까지의 가장 긴 증가하는 수열을 저장하고자 dp에 길이와 수열을 저장하는 이중 리스트로 만들었다.
앞에서부터 각 위치까지 앞에 작은 수가 있고, 수열 길이가 길다면 업데이트하게끔 했고, 만약 업데이트가 한번도 안 되었다면 == 내가 가장 작은 수라면 나 자신을 갖는 수열로 해주었다.
마지막 수열 길이를 기준으로 내림차순 정렬을 해주어 맨 앞에 있는 수열을 찾아 출력하였다.

import sys
input = sys.stdin.readline

def solve():
    global n, arr
    dp = [[0, []] for _ in range(n)]
    dp[0][0] = 1
    dp[0][1] = [arr[0]]
    for i in range(1, n):
        for j in range(i):
            if arr[i] > arr[j]:
                if dp[j][0] + 1 > dp[i][0]:
                    dp[i][0] = dp[j][0] + 1
                    dp[i][1] = dp[j][1] + [arr[i]] 
        if dp[i][0] == 0:
            dp[i][0] = 1
            dp[i][1] = [arr[i]]
            
    dp.sort(reverse = True)
    
    print(dp[0][0])
    for i in dp[0][1]:
        print(i, end = ' ')
    
n = int(input())
arr = list(map(int, input().split(' ')))
solve()

0개의 댓글