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

문제

---

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

11055번: 가장 큰 증가 부분 수열

 

생각의 흐름

---

각 자리에 있는 수를 선택하였을 때 올 수 있는 가장 큰 합을 dp 리스트에 저장한다. 예를 들어, 문제에서 예시로 주어진 arr = [1, 100, 2, 50, 60, 3, 5, 6, 7, 8]의 경우 dp = [1, 101, 3, 53, 113, 6, 11, 17, 24, 32]가 된다. 이 중 max를 출력하면 정답이다. 

각 자리에 올 수 있는 수 중 어떤 수가 max인지를 알기 위해선 이중 for문을 사용하여야 한다. 예를 들어 50의 경우 2~0까지의 인덱스들과 비교하여 해당 수가 50보다 작다면 리스트 s에 값을 넣어준다. 2는 50보다 작으니 s = [53]이 되고 다시 100은 50보다 크니 넘어간다. 1은 50보다 작으니 s = [53, 51]이 되고 max(s)는 53이므로 dp[3]=53이 된다.

 

코드

---

# 백준 11055
import sys

N = int(input())
arr = list(map(int, input().split()))
dp = [0]*N
if N == 1:
    print(arr[0])
    sys.exit()
dp[0]=arr[0]
for i in range(1,N):
    s = []
    for j in range(i-1,-1,-1):
        if arr[j]<arr[i]:
            s.append(arr[i]+dp[j])
    if s:
        dp[i]=max(s)
    else:
        dp[i]=arr[i]
print(max(dp))