[BOJ/python] 11055: 가장 큰 증가하는 부분 수열

문제

✔️ silver 2

문제 흐름

수열을 앞부터 순회하면서 i번째 수를 포함한 경우의 최대 증가 부분 수열 합을 구한다. ➡️ DP
i번째 수를 포함한 경우의 최대 증가 부분 수열의 합 이라고 하니 굉장히 길고 이해가 안 될 수도 있다.
내가 샘플로 계산했던 인풋은 아래와 같다.
문제의 예제 입력과 비슷하지만 마지막을 조금 바꿔봤다.

처음에는 단순하게 앞 숫자만 비교하며 계산해나가는 방식을 선택했으나,
이 문제는 그렇게 적은 시간복잡도로는 해결되지 않았다.
바로 앞만 봐서는 그 전에 현재 값보다 큰 숫자가 있었는지 알 수 없기 때문에 증가하는 부분 수열인지 확인할 방법이 없기 때문이다.
그래서 내가 사용한 방법은 다음과 같다.

1. list memo를 입력 수열으로 초기화한다.
2. 최종 결과(최대 증가 부분 수열 합)을 담을 res를 0으로 초기화한다.
3. i(1 ~ n)에 대해 반복하며 memo[i]의 값을 계산하기 위해서, j(0 ~ i-1)에 대해 아래를 반복한다.
   3-2. 만약 seq[j] < seq[i]인 경우 (증가 수열인 경우), memo[j] + seq[i]를 구한다.
   3-3. 만약 seq[j] >= seq[i]라면 (증가 수열이 아닌 경우), 그대로 memo[j]값을 사용한다.
   3-4. 이렇게 모든 j에 대해 반복하여 구한 값들에 대해 최대값을 구하여 memo[i]에 저장한다.
4. 모든 i에 대해 구한 memo값들 중 최대값을 리턴한다.

최종적으로 시간복잡도는 O(N^2)이 된다.

코드

# 가장 큰 증가하는 부분 수열
# dp

import sys
input = sys.stdin.readline

def dp (seq: list):
    n = len(seq)
    memo = [seq[i] for i in range(n)]
    res = seq[0]

    for i in range(1, n):
        max_val = 0
        for j in range(0, i):
            if seq[j] < seq[i]:
                value = memo[j] + seq[i]
                if value > max_val:
                    max_val = value
                memo[i] = max_val
        if memo[i] > res:
            res = memo[i]
    # print(*memo)
    return res

if __name__ == "__main__":
    n = int(input())
    seq = list(map(int, input().split()))

    result = dp(seq)
    print(result)

마무리

오랜만에 알고리즘 문제를 풀었더니 확실히 감도 많이 죽고 자신감도 없어졌다.. ㅜㅜ
알고리즘도 다시 꾸준히 병행하며 풀어줘야겠다.