[백준] 11055 - 가장 큰 증가 부분 수열 [Python(파이썬)]

문제

www.acmicpc.net/problem/11055

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

풀이

n = 1000이며, 시간 제한이 1초이므로 대략 O(n^2)시간의 알고리즘을 설계하면 해결할 수 있는 문제다. dp테이블은 입력으로 주어진 수열과 동일하게 초기화시킨다.

 

i가 인덱스 0부터 n-1까지 순회하고, j는 인덱스 0부터 i-1까지 순회한다.

이 과정에서 수열[i]와 수열[j]를 비교하고, 수열[i]가 더 크다면 현재 dp[i]와 dp[j]+a[i]를 비교하여 더 큰 값을 취한다.

따라서 각 dp테이블의 값엔 가장 큰 증가 부분 수열의 합이 들어가게 된다.

 

코드

import sys

n = int(sys.stdin.readline().strip())
a = [int(x) for x in sys.stdin.readline().split()]
dp = a[:]

for i in range(n):
    for j in range(i):
        if a[i] > a[j]:
            dp[i] = max(dp[i], dp[j] + a[i])

print(max(dp))