[백준/Python]11055: 가장 큰 증가하는 부분수열

문제

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

백준 문제집 - 0x10강 - 다이나믹 프로그래밍

 

알고리즘: 다이나믹 프로그래밍

---

풀이

수열 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의 합이 가장 큰 증가하는 부분 수열의 합을 출력한다.

 

11053: 가장 긴 증가하는 부분수열과 비슷한 문제다.

N만큼의 dp리스트를 생성 후 이중 for문을 통해 체크한다.

dp[i] = i번째 숫자를 선택했을때의 최댓값

0번째 숫자를 선택했을때의 최댓값은 "0번째 숫자" 외에는 없으므로, dp[0]에 A[0]을 할당한 뒤에 시작한다.

 

1부터 N-1번째 숫자까지 dp를 채워넣는다. ← 첫번째 for문

그리고 각 숫자마다 현재 숫자 이전까지의 dp를 체크해야한다. ← 두번째 for문

 

현재숫자를 i, 0부터 이전숫자까지를 j라고 했을때 A[j] < A[i]라면 증가하는 수열이므로, dp[i]를 (현재까지의 최댓값 dp[i], j까지의 최댓값 dp[j] + 현재 숫자) 중 더 큰 값으로 업데이트한다.

만약 A[j] → A[i] 가 증가하는 수열이 아니라면 (현재까지의 최댓값 dp[i], 현재 숫자 A[i]) 중 더 큰 값으로 업데이트한다.

A[j]의 범위는 0 ~ i-1 이므로 현재 A[j] 외에 A[j] < A[i] 를 만족하는 j값이 있을 수 있기 때문이다.

 

마지막으로 모든 dp중 최댓값을 출력한다.

 

전체 코드

# 메모리: 31120KB / 시간: 204KB
from sys import stdin


input = stdin.readline

N = int(input())
A = list(map(int, input().split()))

dp = [0] * N
dp[0] = A[0]

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])
        else:  # A[i] < A[j]
            dp[i] = max(dp[i], A[i])

print(max(dp))

오랜만의 DP 문제다... DP는 초기에 기준값을 잘 설정하는것이 관건인데, 참 어렵다ㅜㅜ