[백준/Python] 14002번 - 가장 긴 증가하는 부분 수열 4

Sujin Lee·2022년 11월 7일
0

코딩테스트

목록 보기
161/172
post-thumbnail

문제

백준 14002번 - 가장 긴 증가하는 부분 수열 4

해결 과정

시행착오

  • 그러한 수열이 여러가지인 경우 아무거나 출력한다. 이게 무슨 뜻이지? = 부분 수열을 출력하라는 뜻..

풀이

import sys

n = int(sys.stdin.readline())
num = list(map(int,sys.stdin.readline().split()))
dp = [1] * n

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

# 부분 수열의 길이
print(max(dp))

arr = []
m = max(dp)
for i in range(n-1,-1,-1):
  if dp[i] == m:
    arr.append(num[i])
    m -= 1

arr.reverse()
print(*arr)
profile
공부한 내용을 기록하는 공간입니다. 📝

0개의 댓글