[Python | 파이썬] 백준 14002 가장 긴 증가하는 부분 수열4

[Python | 파이썬] 백준 14002 가장 긴 증가하는 부분 수열4

 

 

이 문제는 dynamic programming을 이용해 풀어야하는 문제이고, 가장 긴 증가하는 부분 수열의 길이와 함께 그 부분 수열을 출력해야한다.

따라서 각 인덱스에 현재 부분 수열의 길이와 현재 인덱스에서 가장 긴 부분 수열을 담은 배열을 저장하고 있어야한다.

처음에는 각각 num[i] 원소 한 개를 배열로 하여 부분 수열의 원소로 갖는 것으로 dp를 초기화해준다.

dp = [[1, [num[i]]] for i in range(x)]

그리고 1번부터 x-1번까지 증가하는 i 인덱스에 대해서 0번부터 i-1번까지 증가하는 j 인덱스를 탐색하며 조건을 만족하면 dp[i]를 갱신한다.

이때 num[i]가 num[j]보다 커야하고, i인덱스까지의 부분 수열의 길이가 j까지의 부분수열의 길이보다 1이상 작은 경우에 대해서 갱신한다. 또한 dp의 두번째 원소에는 배열이 들어가야하므로 

dp[i] = [dp[j][0]+1, dp[j][1] + [num[i]] 

이렇게 초기화해준다.

그리고 부분 수열의 길이가 가장 큰 인덱스에 대해서 그 길이인 dp[i][0]과 부분수열 dp[i][1]을 출력해주면된다.

 

x = int(input())
num = list(map(int, input().split()))
dp = [[1, [num[i]]] for i in range(x)]

for i in range(1, x):
    for j in range(i):
        if num[j] < num[i] and dp[i][0] < dp[j][0] + 1:
            dp[i] = [dp[j][0]+1, dp[j][1] + [num[i]]]

max_value = 0
rst = 0
for i in range(x):
    if dp[i][0] > max_value:
        rst = i
        max_value = dp[i][0]
print(max_value)
print(' '.join(map(str, dp[rst][1])))

 

https://www.acmicpc.net/problem/14002

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