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

🥚문제

---

🥚입력/출력

---

🍳코드

import sys
input = sys.stdin.readline

n = int(input().strip())
a = [0] + list(map(int, input().split()))

# dp[x] = x번 인덱스까지의 가장 큰 부분수열의 합
# x번 인덱스까지의 가장 "작은" 부분수열의 합은 a[x]일 것! (길이가 1)
# dp[x] = a[x]로 초기화한다
dp = a[:]

for i in range(1, n+1):
    #print(i, "번 인덱스까지의 가장 큰 부분수열의 합 구하기")
    for j in range(1, i):
        if a[j] < a[i]:  # 증가하는 수열일 때
            #print(j, "번 인덱스 뒤에", i, "번 인덱스가 올 때 합은", dp[j] + a[i])
            dp[i] = max(dp[i], dp[j] + a[i])
    # print(dp)
    # print('-'*20)
print(max(dp))

# 예시
# 8
# 3 10 2 7 11 5 13 8
# 3 + 10 + 11 + 13 = 37이 되어야 함

---

🧂아이디어

DP, 증가 부분 수열

• 증가 부분 수열을 활용하는 또 다른 문제

• 이번에는 증가 부분 수열 중 합이 가장 큰 것을 찾는 게 포인트

• dp[x]에 x번 인덱스까지의 가장 큰 부분 수열의 합을 저장

• 초기화는 dp = a[:]로 하는데, 이는 x번 인덱스까지의 가장 "작은" 부분 수열의 합을 넣어둔 것.
  • x번 인덱스까지의 가장 작은 부분수열은 a[x]만을 수열로 갖는, 길이가 1인 수열!

• i번째 인덱스까지의 가장 큰 부분 수열의 합을 구하기 위해서는
  • j가 (1번째 ~ i-1번째) 인덱스까지일 때 a[j] < a[i]라면, 증가하는 수열을 만족
  • 이 때 dp[i]의 값보다 dp[j](j번째 인덱스까지의 가장 큰 부분 수열) + a[i]의 값이 크다면 갱신해주면 된다.

(예시)
8
3 10 2 7 11 5 13 8
일 때 🔽

1 번 인덱스까지의 가장 큰 부분수열의 합 구하기
[0, 3, 10, 2, 7, 11, 5, 13, 8]
--------------------
2 번 인덱스까지의 가장 큰 부분수열의 합 구하기
1 번 인덱스 뒤에 2 번 인덱스가 올 때 합은 13
[0, 3, 13, 2, 7, 11, 5, 13, 8]
--------------------
3 번 인덱스까지의 가장 큰 부분수열의 합 구하기
[0, 3, 13, 2, 7, 11, 5, 13, 8]
--------------------
4 번 인덱스까지의 가장 큰 부분수열의 합 구하기
1 번 인덱스 뒤에 4 번 인덱스가 올 때 합은 10
3 번 인덱스 뒤에 4 번 인덱스가 올 때 합은 9
[0, 3, 13, 2, 10, 11, 5, 13, 8]
--------------------
5 번 인덱스까지의 가장 큰 부분수열의 합 구하기
1 번 인덱스 뒤에 5 번 인덱스가 올 때 합은 14
2 번 인덱스 뒤에 5 번 인덱스가 올 때 합은 24
3 번 인덱스 뒤에 5 번 인덱스가 올 때 합은 13
4 번 인덱스 뒤에 5 번 인덱스가 올 때 합은 21
[0, 3, 13, 2, 10, 24, 5, 13, 8]
--------------------
6 번 인덱스까지의 가장 큰 부분수열의 합 구하기
1 번 인덱스 뒤에 6 번 인덱스가 올 때 합은 8
3 번 인덱스 뒤에 6 번 인덱스가 올 때 합은 7
[0, 3, 13, 2, 10, 24, 8, 13, 8]
--------------------
7 번 인덱스까지의 가장 큰 부분수열의 합 구하기
1 번 인덱스 뒤에 7 번 인덱스가 올 때 합은 16
2 번 인덱스 뒤에 7 번 인덱스가 올 때 합은 26
3 번 인덱스 뒤에 7 번 인덱스가 올 때 합은 15
4 번 인덱스 뒤에 7 번 인덱스가 올 때 합은 23
5 번 인덱스 뒤에 7 번 인덱스가 올 때 합은 37
6 번 인덱스 뒤에 7 번 인덱스가 올 때 합은 21
[0, 3, 13, 2, 10, 24, 8, 37, 8]
--------------------
8 번 인덱스까지의 가장 큰 부분수열의 합 구하기
1 번 인덱스 뒤에 8 번 인덱스가 올 때 합은 11
3 번 인덱스 뒤에 8 번 인덱스가 올 때 합은 10
4 번 인덱스 뒤에 8 번 인덱스가 올 때 합은 18
6 번 인덱스 뒤에 8 번 인덱스가 올 때 합은 16
[0, 3, 13, 2, 10, 24, 8, 37, 18]
--------------------