백준 14002 파이썬 : 가장 긴 증가하는 부분 수열 4

 

https://www.acmicpc.net/problem/14002

14002번: 가장 긴 증가하는 부분 수열 4

< 소스 코드 >

n= int(input())
array = list(map(int,input().split()))


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

x = max(dp)
print(x)
i = dp.index(x)

result = []
print("dp",dp)
##
for i in range(n-1,-1,-1):
  if dp[i] == x:
    result.append(array[i])
    x -= 1

result.reverse()
print(*result)

< 출력 >

< 설명 >

dp 배열은 가장 긴 증가하는 수열의 크기를 값으로 갖는다.

array 를 돌면서 전체를 체크해, 현 요소보다 작은 값의 개수를 구해, dp 해당 위치에 반영한다.

dp 배열 중 최대값이 첫번째 답이고, dp 배열 끝부터 그 최대값과 같은 dp[] 값에 해당하는 array 요소를

추가하되... 수열 하나 구했으니 하나 뺀 값과 dp[] 값이 일치하는 array 요소를 구하면서...

전체 가장 긴 증가하는 수열의 요소들을 구한다. (두번째 답)

 

설명에 쏘울이 조금 부족한 것 같지만.... 최선을 다했다.🥹