[백준알고리즘] 11055번: 가장 큰 증가 부분 수열 -Python

[백준알고리즘] 11055번: 가장 큰 증가 부분 수열 -Python

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

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

이전 문제인 "가장 긴 증가하는 부분 수열" 문제와 유사하다.

 

이번 문제는 길이가 아니라 부분 수열의 원소들의 합을 구하는 문제라는 차이가 있다. 따라서 이전 문제에서는 길이를 추가한 것을 구하기 위해 +1을 했다면 이번에는 크기를 추가한 것을 구하기 위해 +seq을 해주었다.

 

마찬가지로 리스트의 크기는 1001로 잡아 1~1000을 표현할 수 있게 했고, 각 원소를 하나씩 뽑아 이전에 나왔던 현재의 값보다 작은 값들 중 누적 값이 최대인 값에 자신을 더했다.

 

import sys

N = int(sys.stdin.readline())
arr = [0] * 1001
sequence = list(map(int, sys.stdin.readline().split()))

for seq in sequence:
    arr[seq] = max(arr[:seq]) + seq

sys.stdout.write(str(max(arr)))

 

이번 문제도 이전 문제와 같이 다른 분들 대부분은 max와 slice를 사용한 대신 크기가 N인 리스트와 이중 for문을 통해서 구했다.

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다