14002
-
[백준] 14002번 가장 긴 증가하는 부분 수열 4 (by Python)Programming/Algorithm 2021. 2. 21. 21:52
문제 이 문제의 원형인 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..