[Baekjoon 11055 / Python / 실버2] 가장 큰 증가하는 부분 수열

문제

import copy

import sys

input = sys.stdin.readline

N = int(input())

numList = list(map(int, input().split()))

dp = copy.deepcopy(numList)

for i in range(1, N):

    for j in range(i):

        if numList[i] > numList[j]:

            dp[i] = max(dp[i], dp[j] + numList[i])

print(max(dp))

 

가장 긴 증가하는 부분 수열(LIS)문제와 거의 흡사한 문제이다. 문제의 원리는 거의 같지만 요구하는 출력값이 다르다. LIS는 수열이 길이를 출력했다면, 이 문제는 수열을 모두 더한 값을 출력한다.

 

dp테이블로 사용하기 위해 deepcopy를 통해 입력받은 수열을 복사한다. 이 값을 시작값으로 수열이 증가할 때마다 dp 테이블 값을 갱신해 주면 된다. deepcopy가 아니라 dp = numList 이런 식으로 복사하면, 두 리스트 객체는 같은 메모리 주소값을 가지기 때문에 하나의 리스트로 취급된다. 즉 dp리스트를 바꾸면 numList 까지 함께 바뀐다. 따라서 각각 다른 메모리 주소공간에 저장되어 다른 객체로 취급되도록 하려면 deepcopy를 이용해야 한다.

 

반복문에서 i는 기준 값, j는 비교할 값들이다. i보다 앞에 있는 값들을 j에 대입하며 하나하나 비교하고, 조건을 만족할 때마다 dp테이블을 갱신한다. 마지막으로 dp 테이블에서 가장 큰 값을 출력해주면 된다.