[백준] 14002번 문제 (가장 긴 증가하는 부분 수열 4) 파이썬(Python) 풀이

n = int(input())
nums = list(map(int, input().split()))
dp = [1] * n

for i in range(n):
    for j in range(i):
        if nums[i] > nums[j]:
            dp[i] = max(1 + dp[j], dp[i])
    
result = []
max_num_dp = max(dp)

print(max_num_dp)

for i in range(n-1, -1, -1):
    if dp[i] == max_num_dp:
        result.append(nums[i])
        max_num_dp -= 1

[print(i, end=" ") for i in reversed(result)]

 

https://honggom.tistory.com/80

[백준] 11053번 문제 (가장 긴 증가하는 부분 수열) 파이썬(Python) 풀이

위 링크 문제와 매우 흡사한 문제이며, 가장 길게 증가하는 부분 수열을 dp를 통해 구하는 부분은 완벽히 똑같다.

 

다른 부분은,

dp를 통해 구한 가장 길게 증가한 증가량의 숫자를 통해 출력을 하는 부분인데,

dp를 통해 구한 값 중 가장 큰 값(max_num_dp)부터 인덱스를 하나씩 감소시켜가며 수열과 일치하면 result에 넣어주고

마지막에 reversed(result)를 출력하면 된다.

reversed() 함수를 쓴 이유는 max_num_dp 부터 숫자를 하나씩 감소 시키며 비교 하기 때문에 마지막에 출력되야 할 숫자가 먼저 들어가기 때문이다.