[Backjoon] 14002 가장 긴 증가하는 부분 수열 4 Python 문제 풀이

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

문제해석

수열을 받으면 그중 길이가 제일 긴 증가하는 수열을 구하는 문제이다.

최장 증가 부분 수열(LIS, Longest Increasing Subsequence) 알고리즘이라는 알고리즘 문제에서 자주 볼 수 있는 것을 사용하여 길이를 구할 수 있다.

이 문제에서는 길이뿐만 아니라 해당 수열까지도 결과값으로 출력해야 한다.

해답코드

#가장 긴 증가하는 부분 수열 4

import sys
input = sys.stdin.readline

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

dp = [1] * n

#최장 부분 증가 수열 길이를 구하는 for문
for current in range(n):
    for before in range(current):
        if array[current] > array[before]:
            dp[current] = max(dp[current],dp[before]+1)

print(max(dp))

#수열 출력을 위한 for문
max_dp = max(dp)
lis = []
for i in range(n-1,-1,-1):
    if dp[i] == max_dp:
        lis.append(array[i])
        max_dp -= 1

lis.reverse()

for i in lis:
    print(i, end=" ")

코드해석

n = 수열의 크기
arr = 수열을 이루고 있는 arr(i)를 담은 배열
dp = arr[i]를 마지막 원소로 가질 때 가장 긴 증가하는 부분 수열의 길이

1. dp[i]의 값을 1로 초기화

2. 현재 위치(current)보다 이전에 있는 원소(before)가 작은지 확인한다. (크거나 같으면 가장 긴 증가하는 부분 수열이 될 수 없음)

3. 작다면, 현재 위치의 이전 숫자 중, dp 최댓값을 구하고 그 길이에 1을 더해주면 된다.