[BOJ 17216 🥈1] 가장 큰 감소 부분 수열 (Python)

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

17216번: 가장 큰 감소 부분 수열

문제

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

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

입력

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

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

출력

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

예제 입력 1

10
1 100 2 50 60 8 7 3 6 5

예제 출력 1

186

 

⭕ CODE

n = int(input())

arr = list(map(int, input().split()))

d = [0] * (1001)

for i in range(n):
    for j in range(i):
        # 감소하고있고 i번째 합이 j번째 합보다 작다면
        if arr[i] < arr[j] and d[i] < d[j]:
            d[i] = d[j]
    # 현재값 더해주기
    d[i] += arr[i]
print(max(d))

✏️ Comment

이전에 비슷한 문제를 dp로 푸는 것이 생각나서 dp로 접근하였다. dp를 생각해 내는 것이 가장 어렵다. 문제 풀이를 보면 크게 어렵지 않지만 그 방법을 생각해 내는 것이 가장 어렵다.

 

• dp 아직 많이 어렵다. 많이 연습하자