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

---

---

---

💡 문제

수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.

입력

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

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

출력

첫째 줄에 수열 A의 합이 가장 큰 증가하는 부분 수열의 합을 출력한다.

---

💭 접근

11053번 가장 긴 증가하는 부분 수열 문제와 비숫하지만 이 문제에선 수열의 길이가 아닌 크기를 구해야하는 문제이다.

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

ex) 예제
i = 1, j = 0
a[1] > a[0] : True
dp = [1 100 2 50 60 3 5 6 7 8]
-> dp = [1 101 2 50 60 3 5 6 7 8]

i = 2, j = 0
a[2] > a[0] : True
dp = [1 101 2 50 60 3 5 6 7 8]
-> dp = [1 101 3 50 60 3 5 6 7 8]

i = 2, j = 1
a[2] > a[1] : False
dp = [1 101 3 50 60 3 5 6 7 8]
-> dp = [1 101 3 50 60 3 5 6 7 8]

i = 3, j = 0
a[3] > a[0] : True
dp = [1 101 3 50 60 3 5 6 7 8]
-> dp = [1 101 3 51 60 3 5 6 7 8]

i = 3, j = 1
a[3] > a[1] : False
dp = [1 101 3 51 60 3 5 6 7 8]
-> dp = [1 101 3 51 60 3 5 6 7 8]

i = 3, j = 2
a[3] > a[2] : True
dp = [1 101 3 51 60 3 5 6 7 8]
-> dp = [1 101 3 53 60 3 5 6 7 8]
...

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

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

---

📒 코드

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

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

print(max(dp))

---

💭 후기

11053번 가장 긴 증가하는 부분 수열 문제를 풀이한 뒤 풀어서 쉽게 해결했던 문제.

---

🔗 문제 출처

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

---