[Python][백준/BOJ] 11053번 : 가장 긴 증가하는 부분 수열

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

11053번: 가장 긴 증가하는 부분 수열

 

내 코드

import sys
input = sys.stdin.readline

n = int(input())
lst = list(map(int, input().split()))
dp = [1 for i in range(n)]

for now in range(n): #현재 비교할 수
    for prev in range(now): #0부터 비교할 수의 직전까지
        if lst[now] > lst[prev]:
            dp[now] = max(dp[now], dp[prev]+1)
            
print(max(dp))

 

DP 완벽 이해

DP 문제에 대해 거부감이 있었던 나는, 늘 DP만 빼고 다른 걸 좀 풀어보자는 식이었다.

그런데 내가 봤던 코테 중 비슷하게 생긴 문제가 있는 것이었다.

알고보니 '가장 긴 증가하는 부분 수열' 시리즈가 따로 있을 만큼 코테에 최적화된 DP 문제인 것 같았다.

그때 열심히 풀었지만 결국 테스트케이스가 틀렸는지 제대로 풀지 못했던 지난날의 나를 반성하며 열심히 이해하며 풀었다. 막상 풀어보니 DP 할만하더라...(!)

 

DP 포인트 : DP list, 실제 숫자가 들어있는 list는 평행세계라고 생각하자

 

dp = [1 for i in range(n)]

DP는 이렇게 DP 배열을 하나 더 만들어주는 것이 포인트이다. 특히 계속 증가하는 수열은 가장 긴 수열의 LEN을 구해야 하므로 처음에 1로 초기화를 시켜준다.

그리고 계속 수를 하나씩 늘려가면서, 지금이랑 이전이랑 비교한다.

MAX(이전의 수) < 지금 수
list[prev] < list[now]

이거일 때 DP[now] = dp[prev]+1 해준다. 

 

수가 [10 20 10 30 20 50] 일 때 dp는 결과적으로 이렇게 변한다.

[1, 1, 1, 1, 1, 1]
[1, 2, 1, 1, 1, 1]
[1, 2, 1, 1, 1, 1]
[1, 2, 1, 3, 1, 1]
[1, 2, 1, 3, 2, 1]
[1, 2, 1, 3, 2, 4]

이게 끝이다. 정말 간단하다.

이전보다 큰 적이 4번 있던 거니까, max(dp)로 4를 출력한다.