BaekJoon 14002번 : 가장 긴 증가하는 부분 수열 (python)

BaekJoon 14002번 : 가장 긴 증가하는 부분 수열 4 (G4 39.486%)

가장 긴 증가하는 부분 수열은 i와 j가 있을 때 (i > j) ,(arr[i] > arr[j])인 조건이 만족할 때 d[i] = d[j] + 1을 할 수 있는 알고리즘을 가지고 있다.

• 만약 해당 조건에 만족해서 d[i]가 업데이트 될 때, d[i] < d[j] + 1 and arr[i] > arr[j]일 때 d[i] = d[j] + 1로 업데이트 하고 position[i] = j 로 업데이트 하면서 이 전의 위치값을 저장하게 된다.
• 제일 처음 position값을 -1로 초기화 한 이유가 따로 있다. 만약 일반적인 방법처럼 0으로 초기화 할 경우 어떤 position값이 인덱스 0을 가리키고 있을 때 position[0]도 0으로 초기화가 되어있기 때문에 마지막 while문에서 무한 루프가 돌게 된다. 물론 트리거를 하나 추가하면 쉽지만 더 쉽게 풀기 위해 초기화를 애초에 -1로 초기화 해준다.

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int,input().split()))
d = [1]*n
position = [-1]*n
for i in range(1,n) :
    for j in range(i) :
        if arr[i] > arr[j] and d[i] < d[j] + 1 :
                d[i] = d[j] + 1
                position[i] = j

print(max(d))
result = list()
index = d.index(max(d))
while index != -1 :
     result.append(arr[index])
     index = position[index]

print(*result[::-1])