백준 - 가장 큰 증가 부분 수열 (Dynamic Programming) / Silver 2 / 11055번

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

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

 

문제

수열 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의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

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

 

예제 입력 1

10
1 100 2 50 60 3 5 6 7 8

예제 출력 1

113

 

풀이

import sys


def solution(n, num_list):
    dp = [num_list[0]]  # 각 자릿수까지의 최대 부분수열의 합

    for i in range(1, n):
        temp = []
        for j in range(i):  # 지금까지 만들어진 dp 리스트를 순회하면서
            if num_list[j] < num_list[i]:  # 만약 num_list의 값이 현재 값보다 작다면
                temp.append(dp[j])  # 그 인덱스에 해당하는 dp 리스트 값을 저장.

        if temp:
            dp.append(max(temp) + num_list[i])  # 현재 값보다 작은 값들 중 가장 큰 dp값을 더함.
        else:
            dp.append(num_list[i])  # 현재 값이 제일 작으면 해당 값만 dp 리스트에 추가.

    return max(dp)


N = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))
print(solution(N, nums))

DP문제를 오랜만에 풀어서 그런지 몰라도 조금 어렵게 느껴졌던 문제이다.

dp 배열을 구성할 때 해당 index까지의 최대 부분 수열의 합으로 구성할 생각을 해야 한다.

그리고 그에 따라 어떻게 구성할지를 생각하면

이전까지의 dp배열 중 최댓값을 선택하여 현재 값과 더해서 구성하면 되는데

다만 입력 리스트에서 현재 값보다 작은 값을 갖는 index들만 따로 저장해서

그 index들에 해당하는 dp 배열 값들만 확인해야 한다.

한 번에 생각하기 어려운 다소 까다로운 조건이라고 생각한다.