[BOJ/python] 11053: 가장 긴 증가하는 부분 수열

문제

✔️ silver 2

문제 흐름

저번엔 가장 큰 증가하는 부분 수열을 풀었는데, 이번엔 "긴"이다.
하지만 "증가하는 부분 수열"이라는 큰 틀은 같기 때문에 비슷한 흐름을 가져갔다.

memo[i]는 i번째 수까지의 수열에서 i번째 수가 가장 큰 증가하는 부분 수열의 최대 길이이다.
거꾸로 되짚어 생각한다면 memo[i]는 입력받은 수열 A(lst)의 i 이전 수이면서 i번째 수보다 더 작은 수인 값들 중, 가장 큰 memo값에 1을 더해 저장하면 된다.

이를 위해서는 앞부터 이 조건들을 확인할 수 밖에 없다.
따라서 이중 for문을 돌게 되고, 시간 복잡도는 O(N^2)이다.
이렇게 구한 memo값들중 가장 큰 값을 출력하면 되겠다.

여러 흐름을 따라 놓친 부분들을 수정해나가며 조건을 찾았다.
그 과정에서 내가 확인했던 예제 인풋은 아래와 같다.

# input 1
6
10 20 10 20 30 50
# output 1
4

# input 2
5
3 4 5 1 2
# output 2
3

# input 3
6
4 6 1 2 3 8
# output 3
4

코드

# 가장 긴 증가하는 부분 수열
# DP

import sys
input = sys.stdin.readline

def dp (lst: list):
    n = len(lst)
    # memo[i] : i번째 수까지의 i번째 수가 가장 큰 증가 부분 수열의 최대 길이
    memo = [0 for i in range(n)]

    for i in range(0, n):
        max_value = 0
        for j in range(0, i):
            if lst[j] < lst[i] and max_value < memo[j]:
                max_value = memo[j]
        memo[i] = max_value + 1
    
    # print( *memo )
    return max(memo)

if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))
    
    result = dp(a)
    print(result)