[백준] 14002번 가장 긴 증가하는 부분 수열 4 - Python / 알고리즘 기초 1/2 - 다이나믹 프로그래밍 1

---

---

---

💡 문제

수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

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

---

💭 접근

11053번 가장 긴 증가하는 부분 수열 문제와 비슷한 문제이지만, 이번에는 길이 뿐만 아니라 가장 긴 부분 수열도 출력해야한다. 수열의 길이를 구하는 법은 위 문제 참고.

1. 부분 수열을 저장할 ans 리스트와 부분 수열의 길이를 저장할 dp 리스트를 선언해 준다.
2. 우선, dp[i]에 a[i]를 마지막 원소로 가지는 부분 수열의 길이를 저장한다.
3. a[i] > a[j] 이고, dp[i]에 저장된 길이가 dp[j] + 1보다 작다면 (이전 수열에서 길어지는 순간) ans[i]에 ans[j]에 a[i]를 붙힌 수열을 저장해준다.

ex) 예제
i = 1, j = 0
a[1] > a[0] : True
dp[1] < dp[0] + 1 : True
dp = [1, 1, 1, 1, 1, 1] -> dp = [1, 2, 1, 1, 1, 1]
ans = [[10], [10, 20], [10], [30], [20], [50]]


i = 2, j = 0
a[2] > a[0] : False
dp[2] < dp[0] + 1 : False
dp = [1, 2, 1, 1, 1, 1] -> dp = [1, 2, 1, 1, 1, 1]
ans = [[10], [10, 20], [10], [30], [20], [50]]


i = 2, j = 1
a[2] > a[1] : False
dp[2] < dp[1] + 1 : False
dp = [1, 2, 1, 1, 1, 1] -> dp = [1, 2, 1, 1, 1, 1]
ans = [[10], [10, 20], [10], [30], [20], [50]]


i = 3, j = 0
a[3] > a[0] : True
dp[3] < dp[0] + 1 : True
dp = [1, 2, 1, 1, 1, 1] -> dp = [1, 2, 1, 2, 1, 1]
ans = [[10], [10, 20], [10], [10, 30], [20], [50]]


i = 3, j = 1
a[3] > a[1] : True
dp[3] < dp[1] + 1 : True
dp = [1, 2, 1, 2, 1, 1] -> dp = [1, 2, 1, 3, 1, 1]
ans = [[10], [10, 20], [10], [10, 20, 30], [20], [50]]


i = 3, j = 2
a[3] > a[2] : True
dp[i] < dp[j] + 1 : False
dp = [1, 2, 1, 2, 1, 1] -> dp = [1, 2, 1, 3, 1, 1]
ans = [[10], [10, 20], [10], [10, 20, 30], [20], [50]]
...

---

📒 코드

n = int(input())
a = list(map(int, input().split()))
dp = [1 for _ in range(n)]
ans = [[a[i]] for i in range(n)]

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

print(max(dp))
print(*ans[dp.index(max(dp))])

---

💭 후기

11053번 가장 긴 증가하는 부분 수열 문제의 연장이라 쉽게 생각했지만 부분 수열을 업데이트하는 조건을 찾는 것이 까다로웠다.

---

🔗 문제 출처

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

---