백준 11055번 파이썬

 

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

풀이

현재의 값보다 작은 수들 중 가장 dp 값이 큰 것을 더하여 dp값을 업데이트 하고 max(dp)를 구한다.

코드

n = int(input())

arr = list(map(int, input().split()))
dp = [0] * n
dp[0] = arr[0]
for i in range(1, n):
        big = 0
        for j in range(i):
            if arr[j] < arr[i] and big < dp[j]:
                big = dp[j]
        dp[i] += big + arr[i]
print(max(dp))

여기서 더 시간적 효율성을 높일 수 있는 다른 풀이도 있다.

풀이2

이미 정렬이 되어있다면? 엄청 쉬울 것이다. 해당 숫자 전까지 리스트 중에서 가장 큰 값을 더하면 그만이다.

이미 값의 범위는 1000이하로 정해져 있어서 배열을 이용하여 1001까지의 배열을 만들어 각각 최댓값(해당 숫자 전까지 리스트 중에서 가장 큰 값)을 구하여 dp배열에 저장한다.

코드

n = int(input())
dp = [0] * 1001
a = list(map(int, input().split()))
for i in a:
    dp[i] = max(dp[:i]) + i
print(max(dp))