[백준] 11722번 가장 긴 감소하는 부분 수열 - Python / 알고리즘 기초 1/2 - 다이나믹 프로그래밍 1 (연습)

---

---

---

💡 문제

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

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

입력

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

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

출력

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

---

💭 접근

11053번 가장 긴 증가하는 부분 수열 문제와 비슷한 문제이지만 이번 문제는 증가하는 부분 수열이 아닌 감소하는 부분 수열의 길이를 구하는 문제이다. 반대로 보면, 입력받은 list a에서 거꾸로 증가하는 부분 수열의 길이를 구하면, 감소하는 부분 수열의 길이를 구할 수 있다. 따라서, a를 반전시켜서 증가하는 부분 수열 길이를 저장해준다.

1. list a를 반전시켜준다.

2. dp[i]는 a[i]를 마지막 원소로 가지는 부분 수열의 최대 크기로 정의한다.

3. 이때 0 ≤ j < i에 대해(i보다 앞에 있는 각각 모든 원소에 대해) 앞의 원소가 더 작을 때 (a[i] > a[j])
   dp[i]를 갱신(dp[i] = max(dp[i], dp[j] + 1))해준다.

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


i = 2, j = 0
a[::-1] = [10 20 20 10 30 10]
a[2] > a[0] : True
dp = [1, 2, 1, 1, 1, 1] -> dp = [1, 2, 2, 1, 1, 1]


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


i = 3, j = 0
a[::-1] = [10 20 20 10 30 10]
a[3] > a[0] : False
dp = [1, 2, 2, 1, 1, 1] -> dp = [1, 2, 2, 1, 1, 1]


i = 3, j = 1
a[::-1] = [10 20 20 10 30 10]
a[3] > a[1] : False
dp = [1, 2, 2, 1, 1, 1] -> dp = [1, 2, 2, 1, 1, 1]


i = 3, j = 2
a[::-1] = [10 20 20 10 30 10]
a[3] > a[2] : False
dp = [1, 2, 2, 1, 1, 1] -> dp = [1, 2, 2, 1, 1, 1]
...

따라서 점화식은 다음과 같이 도출할 수 있다.

dp[i] = max(dp[i], dp[j] + 1)

---

📒 코드

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

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

print(max(dp))

---

💭 후기

계속해서 LIS 유형의 문제를 풀고 연습해왔기 때문에 어렵지 않게 해결할 수 있었다.

---

🔗 문제 출처

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

---