14002_가장 긴 증가하는 수열

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

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

 

 

다시 돌아온 dp파트이다.

 

이전에 가장 긴 증가하는 부분수열의 개수만 구하는 코드를 짠 적이 있는데 이번에는 그 수열자체를 구하는 코드이다.

 

하지만 첫번째 줄부터 기록해나가면서 작성하는 방법인데는 변함이 없다

 

1 2 1 3 2 5 

 

라고 생각해보자.

 

그리고 dp를 [ [1] [2] [1] [3] [2] [5] ] 이렇게 만들어보자.

 

그리고 첫번째부터 dp를 추가해 나갈 것이다.

 

처음은 건들게 없으니 넘어가고 2번째 2를 보자. 2는 1보다 크고, dp의 개수도 더 작지않기에 1의 배열을 그대로 가져와서 뒤에 2를 붙일 수 있다. 즉,

 

[ [1] [1,2] [1] [3] [2] [5] ] 가 된다. 3번째 1은 앞의 2개의 dp를 합칠 수 없다. 숫자가 1,2,라서 더큰수가 없기때문 즉

 

 

[ [1] [1,2] [1] [3] [2] [5] ] 그대로가 된다.

 

그다음 3을 만나면 이제 비교해나가면된다. 이전 배열중에서 2배열이 가장 길이가 길기때문에 해당 배열에 3을 더하면 된다. 즉,

[ [1] [1,2] [1] [1,2,3] [2] [5] ] 

 

같은 방법으로 반복하면

 

 

[ [1] [1,2] [1] [1,2,3] [1,2] [5] ] 

 

[ [1] [1,2] [1] [1,2,3] [1,2] [1,2,3,5] ]  와같이 나올 것이다.

 

그러면 해당 배열에서 가장 길이가 긴 부분이 정답이 될 것이다.

 

 

n = int(input())
lst = list(map(int,input().split()))
dp = [[lst[i]] for i in range(n)]
for i in range(1,n):
    for j in range(i-1,-1,-1):
        if lst[i] > lst[j] and len(dp[j]) >= len(dp[i]):
            dp[i] = dp[j] + [ lst[i] ]

result = max(dp,key=len)
print(len(result))
for i in result:
    print(i,end=' ')