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

DP 개념 바로가기

문제

가장 긴 증가하는 부분 수열 4 문제 링크

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

6
10 20 10 30 20 50

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

둘째 줄에는 가장 긴 증가하는 부분 수열을 출력한다. 그러한 수열이 여러가지인 경우 아무거나 출력한다.

4
10 20 30 50

접근 방식

dp1값은 현재 수가 끝인 부분 수열의 최대 길이
dp2값은 현재 수 바로 전의 인덱스 값

1. dp1과 dp2 테이블을 생성하고 각각 1과 -1로 초기화 한다

2. 반복문으로 수열을 처음부터 검사한다

3. 현재 수가 이전 수보다 크고 이전 수의 dp1값에 1을 더한 값이 현재 dp1값보다 크면 dp1 값을 이전 수의 dp1값에 1을 더한 값을 대입하고 이전 수의 인덱스를 dp2에 추가한다

4. max(dp1) 값이 증가하는 부분 수열의 최대 길이이다

5. 증가하는 부분 수열은 가장 큰 dp1 값의 인덱스를 사용하여 dp2에서 내려가면서 큰 값부터 구하고 뒤집는다

코드

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

dp1 = [1] * n
dp2 = [-1] * n

for i in range(1, n):
    for j in range(i):
        if num_list[i] > num_list[j] and dp1[i] < dp1[j] + 1:
            dp1[i] = dp1[j] + 1
            dp2[i] = j


answer = []
idx = dp1.index(max(dp1))

while idx != -1:
    answer.append(num_list[idx])

    idx = dp2[idx]

print(max(dp1))
print(' '.join(map(str,answer[::-1])))