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

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

 

📝 문제

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

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

 

📜 풀이

• LIS 알고리즘을 사용해 풀이할 수 있음
• 다만 LIS의 길이만 출력하는 것이 아닌 수열 자체도 출력해야 함
• 이를 위해서는 DP 배열에 저장된 값이 해당 요소가 포함된 증가하는 부분 수열에서 몇 번째 요소인지를 나타낸다는 것을 이해해야 함
• 문제에 제시된 예제를 예로 들면, A = [10, 20, 10, 30, 20, 50]에서 DP 배열은 [1, 2, 1, 3, 2, 4]의 형태로 나타나며, 이때 DP[2]의 의미는 A[2]의 요소가 증가하는 부분 수열에서 두 번째 요소라는 것
• 이러한 특성을 이용하여 배열의 뒤에서부터 탐색을 진행하며, 내림차순으로 차례대로 이어지는 원소들을 저장한 뒤 출력해주면 된다.(길이가 같다면 아무 수열이나 출력해도 되기 때문)

 

💻 소스코드

n = int(input())
a = list(map(int, input().split()))
dp = [1] * n

for i in range(n):
    for j in range(i):
        if a[i] > a[j]:
            dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))

LIS = []
cnt = max(dp)
for i in range(n - 1, -1, -1):
    if dp[i] == cnt:
        LIS.append(a[i])
        cnt -= 1

LIS.reverse()
print(*LIS)