백준 11055 파이썬

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

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

 

정답 코드 

from sys import stdin

read = stdin.readline

N = int(read())
arr = list(map(int, read().split()))

dp = [0] * N
dp[0] = arr[0]
for i in range(1, N):
    dp[i] = arr[i]
    for j in range(i):
        if arr[j] < arr[i]:
            dp[i] = max(dp[i], dp[j] + arr[i])

print(max(dp))

 

 

다른 정답 코드 (속도 빠름)

이런 식의 풀이가 꽤 보이던데 애초에 dp 배열의 크기를 1001 (N 최대 크기)으로 잡고 시작한다.

 

import sys

input = sys.stdin.readline

n = int(input())
dp = [0] * 1001

max_num = 0
data = list(map(int, input().split()))

for i in data:
    dp[i] = i
    dp[i] += max(dp[:i])
print(max(dp))

입력으로 받은 값이 저장된 data 의 각 원소들을 dp 에 할당 한다. 0번 인덱스부터 순차적으로 쌓는 것이 아니라, 해당 값의 크기를 인덱스로 잡아서 dp 배열에 할당한다 (ex i = 100 이면, dp[100] = 100 )

그리고 해당 dp[i] 의 값을 dp[:i] 의 값중 가장 큰 것을 골라 더하여 dp[i] 를 업데이트 한다.

이렇게 되면 굳이 증가하는 수열인지 검사할 필요가 없어진다. 그로 인해 이중 for 문도 없앨 수 있어 더 빠른 연산 속도를 낼 수 있다.