백준 14002번 : 가장 긴 증가하는 부분 수열 4 in Python

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

 

www.acmicpc.net

이 문제는 주어진 수열에 대해 가장 긴 증가하는 부분 수열의 길이와 그 수열을 구하는 문제이다.

이를 해결하기 위해서는 dynamic programming을 이용해야 하고, 더불어 나중에 부분 수열을 출력하기 위한 배열을 따로 추가해야 한다.

우선 각 배열의 값이 해당 값을 포함하는 증가하는 부분 수열 중 가장 긴 부분 수열의 길이를 의미하는 dp 배열을 만들고, 각 배열의 값이 가장 긴 증가하는 부분 수열 내에서 자기 앞에 있는 수에 해당하는 인덱스를 의미하는 record 배열을 만든다. 예를 들어 수열이 [10, 20, 10, 30, 20, 50]으로 주어져 있는 경우 dynamic programming을 거치면 dp는 [1, 2, 1, 3, 2, 4], record는 [0, 0, 2, 1, 2, 3]이 된다. 하나의 예시로 record[5] = 3은 5번째 인덱스에 해당하는 50을 포함하는 가장 긴 증가하는 부분 수열에서 50 앞에 있는 값이 3번째 인덱스에 있는 30임을 의미한다.

그 다음 1번째 인덱스부터 N-1번째 인덱스까지 순회하면서 각 인덱스 i보다 작은 모든 인덱스 j에 대해 A[j]가 A[i]보다 작은 경우 증가하는 부분 수열을 만들 수 있고, 이렇게 만든 부분 수열 중 가장 긴 부분 수열을 골라야 하므로 dp[i]는 dp[j] + 1 중 가장 큰 값으로 한다. 이때 가장 큰 값이 나온 경우의 j를 record[i]에 기록한다.

그런 다음 dp의 모든 원소들 중 가장 큰 값을 가지는 원소를 뽑고, 이 원소의 인덱스를 따로 저장한다. 즉, 가장 긴 증가하는 부분 수열의 길이와 해당 부분 수열의 마지막 원소가 A의 어느 위치에 존재하는지를 알아낸다. 그러면 우선 부분 수열의 길이는 구했고, 부분 수열을 출력할 때는 따로 저장한 마지막 원소의 인덱스와 record 배열을 이용한다.

이를 코드로 구현하면 다음과 같다.

N = int(input())
A = list(map(int, input().split()))
# 가장 긴 증가하는 부분 수열의 길이을 저장하기 위한 배열
dp = [1 for _ in range(N)]
# 가장 긴 증가하는 부분 수열을 출력하기 위해 인덱스를 기록하는 배열
record = [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
            record[i] = j
max_len = 0
fin_idx = 0
# 가장 긴 증가하는 부분 수열의 길이와 마지막 원소의 위치를 저장한다.
for i in range(N):
    if max_len < dp[i]:
        max_len = dp[i]
        fin_idx = i
print(max_len)
def print_record(n):
    if n == record[n]:
        return str(A[n])
    return print_record(record[n]) + " " + str(A[n])
print(print_record(fin_idx))