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

---

💭 접근

이와 같은 문제 유형을 LIS(Longest Increasing Subsequence)로 부른다. LIS를 해결하는 방법으론 완전탐색, DP, 이진 탐색 등이 있는데, 이 문제는 입력이 N (1 ≤ N ≤ 1,000) 이므로 DP를 사용하여 해결하였다.

1. dp[i]는 a[i]를 마지막 원소로 가지는 부분 수열의 최대 길이로 정의한다.
2. 이때 0 ≤ j < i에 대해(i보다 앞에 있는 각각 모든 원소에 대해) 앞의 원소가 더 작을 때 (a[i] > a[j])
   dp[i]를 갱신(dp[i] = max(dp[i], dp[j] + 1))해준다.

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


i = 2, j = 0
a[2] > a[0] : False
dp = [1, 2, 1, 1, 1, 1] -> dp = [1, 2, 1, 1, 1, 1]


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


i = 3, j = 0
a[3] > a[0] : True
dp = [1, 2, 1, 1, 1, 1] -> dp = [1, 2, 1, 2, 1, 1]


i = 3, j = 1
a[3] > a[1] : True
dp = [1, 2, 1, 2, 1, 1] -> dp = [1, 2, 1, 3, 1, 1]


i = 3, j = 2
a[3] > a[2] : True
dp = [1, 2, 1, 2, 1, 1] -> dp = [1, 2, 1, 3, 1, 1]
...

---

📒 코드

n = int(input())
a = list(map(int, input().split()))
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))

---

💭 후기

dp를 어떻게 정의할지, 점화식을 어떻게 세울지 많이 까다로웠던 문제였다.

---

🔗 문제 출처

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

---