[백준/Python] 11055번 가장 큰 증가 부분 수열

출처 : google

 

-문제

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

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

 

-가장 간단한 풀이 : 완전 탐색&DP

예제를 보면서 풀어봐요

 

저는 가장 직관적으로 생각할 수 있는 풀이에 아주 조금의 변형을 가미해 문제를 풀었어요.

먼저 arr 라는 이름의 리스트에 0과 주어진 수열을 저장해요.

arr=[0]
arr += list(map(int, input().split()))

arr = [0, 1, 100, 2, 50, 60, 3, 5, 6, 7, 8]

 

그리고 인덱스를 1부터 n까지 조사하며 dp 리스트에 각 인덱스의 값을 포함하는 증가 부분 수열 중 합이 최대인 경우를 저장했어요.

즉 dp[i] = 'arr[i]까지의 증가하는 부분 수열 중 합이 최대인 경우'라고 할 수 있어요.

 

dp 리스트를 채워나가기 위해서, 현재 주목하고 있는 인덱스의 arr 값보다 인덱스도 작고 값도 작은 원소들의 dp 값을 비교하고 그 최댓값을 현재 arr의 수와 더해주면 돼요.

 

n이 최대 1000까지 밖에 주어지지 않고, 인덱스 i에 대해 조사해야 할 경우도 i횟수이기에 수행해야 할 연산은 O(n^2)이에요. 그래서 주어진 시간은 가뿐히 통과할 수 있어요.

 

-가장 간단한 풀이의 소스코드

import sys
input = sys.stdin.readline

n = int(input())
arr=[0]
arr += list(map(int, input().split()))


dp = [0] * (n+1)
dp[1] = arr[1]
for i in range(2, n + 1):
    temp = 0
    for j in range(i, -1, -1):
        if arr[j] < arr[i]:
            if dp[j] > temp:
                temp = dp[j]
        
    dp[i] = temp + arr[i]    
print(max(dp))