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

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

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

아직 코드가 매우 지저분하다..

그래도 어찌저찌 여러번 시도끝에 성공..

 

 

피드백은 언제나 환영입니다 :)

 

import sys

N = int(input())

seq = list(map(int,input().split()))

 

result = []

 

dp = [[0,i] for i in range(N)]

 

# dp[0][0] = 0

for i in range(N):

  for j in range(i):

      if seq[i] > seq[j] and dp[i][0]<dp[j][0]:

        dp[i][0] = dp[j][0]

        temp = seq[j]

        # result.append(temp)

  

  dp[i][0] += 1

 

# print(dp)

mm = (max(dp))[0]

# print(mm)

maxdp = (max(dp))[0]

maxdpind = (max(dp))[1]

 

onlydp = []

for i in range(N):

    onlydp.append(dp[i][0])

 

# onlydp.reverse()

while dp:

    

  

    temp = onlydp[0:maxdpind+1]

    temp.reverse()

    maxdpind = abs(temp.index(maxdp) - (len(temp)-1))

  

    a,ind = dp.pop(-1)

    onlydp.pop(-1)

  

    if ind==maxdpind:

        s = seq.pop(ind)

        result.append(s)

        maxdp -= 1

        

     

    if len(result) == mm:

        break   

 

print(len(result))

result.reverse()

print(*result)

 

 

-> dp의 각 원소를 [dp값, index] 이런 리스트로 잡았는데 그냥 dp값만 하는게 훨씬 편하고 간편했을 것 같다.