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

[Gold IV] 가장 긴 증가하는 부분 수열 4 - 14002

문제 링크

분류

다이나믹 프로그래밍(dp)

문제 설명

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

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

입력

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

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

출력

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

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

---

풀이 🔓

일단 너무 아쉽다… 이때까지 봤던 코테 문제중에 이러한 유형이 써야하는 경우가 많았는데 구현을 못 했던 기억이 있다 ㅠ

1. 가장 긴 증가하는 부분 수여의 크기를 구하는 방법을 사용한다

• 현재 원소가 앞에 원소들과 비교했을 때 몇 번째인지 기록하는 dp를 만든다
• ex) [10 ,20, 10, 30, 20, 50] -> [1, 2, 1, 3, 2, 4]

1. 가장 긴 증가하는 부분 수열을 출력하기 위해서 dp의 맨 뒤에서 부터 순서대로 구한다

---

코드 📃

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

# 가장 긴 증가하는 부분순열의 크기
dp = [1] * n

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


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

res.reverse()
print(max(dp))
for i in res:
    print(i, end=' ')