[백준] 14002 가장 긴 증가하는 부분 수열 4 - DP (Python)

DP 문제를 열심히 풀기 시작한 나예요

11053 가장 긴 증가하는 부분 수열을 제법 내 힘으로 풀고 자신감이 생겨서 연계된 문제인 가장 긴 증가하는 부분 수열 4 문제를 풀었다. 겁도 없이 골드 문제를 손댄 죄...

Solution

n = int(input())

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

dp = [1] * n
result = []

for i in range(n) :
    for j in range(i) :
        if list[i] > list[j] :
            dp[i] = max(dp[i] ,dp[j]+1) # i 에서의 최적의 해를 갱신해준다.
            
max_length = max(dp) # 가장 긴 증가하는 부분의 길이

- 먼저 가장 긴 증가하는 부분 수열의 길이를 구한다.

m = max_length # 복원!!!!!!

for i in range(n-1, -1, -1):
    if dp[i] == m :
        result.append(list[i])
        m -= 1
result.reverse()
print(max_length)
print(" ".join(map(str, result)))

- 그 다음 다른 변수로 max_length 를 복원해둔다. 이따 마지막에 출력해야 하기 때문이다. 

- dp 배열을 거꾸로 순회한다.

- dp[i] 가 m 과 같다는 것은 증가하는 부분 수열이라는 의미이기 때문에 그 인덱스를 가진 list 의 값을 추가해준다.

- m 을 1 씩 줄여주면 다음 찾을 요소의 길이를 갱신할 수 있다. dp 리스트에서 증가하는 수열의 길이는 1 이기 때문이다.

전체 Code

# import sys
# input = sys.stdin.readline

n = int(input())

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

dp = [1] * n
result = []

for i in range(n) :
    for j in range(i) :
        if list[i] > list[j] :
            dp[i] = max(dp[i] ,dp[j]+1) # i 에서의 최적의 해를 갱신해준다.
            
max_length = max(dp) # 가장 긴 증가하는 부분의 길이
m = max_length # 복원!!!!!!

for i in range(n-1, -1, -1):
    if dp[i] == m :
        result.append(list[i])
        m -= 1
result.reverse()
print(max_length)
print(" ".join(map(str, result)))