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

백준 14002번

최종 제출 코드

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

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

result = []
index = max(dp)
k = len(dp)-1

while index > 0:
  if dp[k] == index:
    result.append(array[k])
    index -= 1
  k -= 1

print(len(result))
print(*reversed(result))

◼ 가장 긴 수열을 구하는 부분은 11053번과 동일

◼ dp 리스트를 이용해서 가장 긴 수열 출력

• 처음에는 인덱스를 0부터 탐색했으나, 가장 긴 수열이 아닌 여러 개의 부분 수열 중 하나일 뿐인 부분 수열을 출력하는 경우가 발생.
• 인덱스를 역으로 탐색하여 큰 수부터 result 배열에 넣는다.