[백준 BOJ / Python] 14002번 가장 긴 증가하는 부분 수열 4 DP

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 문제이다.

풀이

• DP를 사용하여 LIS를 구하는 기존 문제에 부분 수열의 길이뿐만 아니라 부분 수열을 요소까지 출력하는 문제이다. 따라서 증가하는 부분 수열의 요소를 담는 것을 함께 구현해야 한다.
• 증가하는 부분 수열의 요소를 담는 리스트를 생성하고 dp가 증가할 때 함께 업데이트 되도록 한다.

알고리즘

1. n과 a 수열을 입력받는다.
2. 1로 초기화된 dp를 생성한다.
3. 부분 수열의 요소를 담을 b 리스트를 생성한다.
4. A 수열에서 뒤의 요소가 앞의 요소보다 크고 부분 수열의 길이도 더 길어질 때, 부분 수열의 길이를 업데이트 하면서 부분 수열의 요소도 업데이트 해준다.
5. 가장 긴 부분 수열의 길이를 찾아 출력하고, 해당 위치와 동일한 부분 수열의 요소를 출력한다.

Python 코드

import sys
input = sys.stdin.readline

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

dp = [1] * n
b = [[a[i]] for i in range(n)]
for i in range(1,n):
    for j in range(i):
        if a[j] < a[i] and dp[i] < dp[j] + 1: 
            dp[i] = dp[j] + 1
            b[i] = b[j]+[a[i]]
m = max(dp)
print(m)
print(*b[dp.index(m)])

[Study/Algorithm] - [알고리즘 / Python] 가장 긴 증가하는 부분 수열 (LIS)

[알고리즘 / Python] 가장 긴 증가하는 부분 수열 (LIS)

문제 출처

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