백준-11055-가장 큰 증가 부분 수열

문제

가장 큰 증가 부분 수열

풀이

문제조건 해석

증가하는 부분 수열 중 수열의 합이 가장 큰 값을 구하는 문제

LIS(가장 긴 증가 부분 수열) 문제와 유사하다. DP로 해결해야 한다.

알고리즘

dp[i] : i를 마지막 항으로 증가하는 부분 수열 중 합이 가장 큰 값

증가하는 부분 수열(arr[j] < arr[i]) 중, 현재 비교기준 값(dp[i])이 이전번째까지의 합(dp[j]) + 자신의 값(arr[i])보다 작을 때, dp[i] = dp[j] + arr[i]를 해준다

코드

n = int(input())
arr = [int(x) for x in input().split()]
dp = arr.copy()
answer = 0
for i in range(n):
    for j in range(i):
        if arr[j] < arr[i] and dp[i] < dp[j] + arr[i]:
            dp[i] = dp[j] + arr[i]
    if answer < dp[i]:
        answer = dp[i]

print(answer)

테스트케이스 입력
10
1 100 2 50 60 3 5 6 7 8

i
1. [1, 100, 2, 50, 60, 3, 5, 6, 7, 8]
2. [1, 101, 2, 50, 60, 3, 5, 6, 7, 8]
3. [1, 101, 3, 50, 60, 3, 5, 6, 7, 8]
4. [1, 101, 3, 53, 60, 3, 5, 6, 7, 8]
5. [1, 101, 3, 53, 113, 3, 5, 6, 7, 8]
6. [1, 101, 3, 53, 113, 6, 5, 6, 7, 8]
7. [1, 101, 3, 53, 113, 6, 11, 6, 7, 8]
8. [1, 101, 3, 53, 113, 6, 11, 17, 7, 8]
9. [1, 101, 3, 53, 113, 6, 11, 17, 24, 8]
10. [1, 101, 3, 53, 113, 6, 11, 17, 24, 32]

배운점

• 점화식으로 나타내지 못하는 DP도 있다.
• 유사 문제
  • 상자넣기(LIS)