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

문제

이 문제의 원형인 11053번에서 꽤나 애를 먹어서 어떻게 꼬아놨을까 조금 긴장했지만 생각외로 쉽게 풀렸던 문제. 경로를 기억해두는 장치만 해두면 되는 문제였다.

 

풀이

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

for i in range(n):
    for j in range(i):
        if arr[i] > arr[j] and dp[i][0] < (dp[j][0] + 1):
            dp[i] = [dp[j][0] + 1, j]

temp = dp.index(max(dp))
route = [temp]

while dp[temp][1] != temp:
    route.insert(0, dp[temp][1])
    temp = dp[temp][1]

print(dp[route[-1]][0])
print(*[arr[r] for r in route], sep=' ')

문제를 풀다가 알게 되는 파이썬 문법이 종종 있는데, 이 문제를 풀면서 2차원 리스트에 max 함수를 쓰면 첫 번째 원소를 기준으로 최댓값 원소를 반환해준다는 것을 알 수 있었다. 배운 것을 잊지 말고, 성장하자🙏