백준 14002: 가장 긴 증가하는 부분 수열 4 - LIS, DP(파이썬)

가장 긴 증가하는 부분 수열 4 성공스페셜 저지

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

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

둘째 줄에는 가장 긴 증가하는 부분 수열을 출력한다. 그러한 수열이 여러가지인 경우 아무거나 출력한다.

 

내 코드

import sys
n=int(sys.stdin.readline())
arr=list(map(int,sys.stdin.readline().split()))

answer=[1]*n

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

big=max(answer)
print(big)

#answer의 끝부분부터 탐색하여 big을 줄여나가며 같은 지점 파악.
pos=[]
for i in range(n-1,-1,-1):
    if answer[i]==big:
        pos.append(i)
        big-=1

pos.sort() #큰 수들의 좌표 먼저 저장되어 있으므로 정렬.

for x in pos:
    print(arr[x],end=' ')

 

 

풀이 및 접근)

- 특정 원소까지의 최대 증가하는 수열의 길이를 최신화 시키며 answer을 채운다.

- i번째 원소에 대해서, 이보다 앞에 있는 원소들에 대해서 i번째 원소가 더 크면, answer[i]를 answer[i]+1로 최신화한다. 그리고 이 과정에서 가장 최대값을 가질 수 있도록 한다.

- 위의 과정을 거치면, answer[ ]에는 각 위치별 최대 길이가 저장되어 있다. 이를 가장 뒤에서부터 탐색하며 big을 줄여나간다. big과 answer[i]의 값이 같아지는 순간의 좌표를 pos[ ] 에 저장한다. 그렇게 되면, pos[ ] 에는 역순으로 수열을 이루는 좌표값들이 들어가 있다.

이를 정렬하여 arr[ ]들의 값을 출력하면 된다.