백준 14002번 파이썬 문제풀이(DP - 가장 긴 증가하는 부분 수열 4)

---

이 문제는 11053번(https://ji-gwang.tistory.com/277) 과 굉장히 비슷하지만 한가지 더 추가되었다. 가장 긴 증가하는 부분 수열을 길이와 함께 같이 출력하라고 한다. 어떻게 접근하면 될까? 많은 시도를 해보던 중 한가지를 발견했다.

 

11053번의 해설에서 dp에 저장 되어 있는 값을 잘 보면 해당 값들은 현재 배열에서 앞 원소들보다 몇번째로 큰 지에 대한 순서를 나타내준다.

 

예를들어 1 3 2 라는 값을 입력한다면 dp에는 [1,2,2] 가 저장이 된다. 그렇다면 1은 1번째, 3과 2는 2번째라는 것을 알 수 있다.

 

또한 문제에서 입력처럼 10 20 10 30 20 50 을 입력한다면 dp에는 [1,2,1,3,2,4]가 저장 된다. 50은 4번째 30은 3번째 20은 2번째 10은 첫번째라는 것을 알 수 있다.즉, 이처럼 dp에 저장되어 있는 값을 입력받은 배열과 매칭시켜서 뽑아주기만 하면 된다. 

 

N = int(input())
input_array = list(map(int, input().split()))
dp = [1] * N  # 최장수열 길이를 저장할 dp 리스트선언

for i in range(N):  # 배열 길이만큼돈다.
    for j in range(i):  # 해당 배열 원소의 직전 원소까지 돈다.
        if input_array[i] > input_array[j]:  # 만약 해당 원소가 전 원소보다 크다면
            dp[i] = max(dp[i], dp[j] + 1)
            # 전 원소에 저장되어 있는 최장수열길이에서 +1 값과 저장되어있는 수열길이값을 비교해서 큰값을 대입

print(max(dp))  # 최장길이 출력

subsequence = [] #정답수열 입력할 배열선언
order = max(dp)  # max(dp) 값을 저장
for i in range(N - 1, -1, -1):
    if dp[i] == order:  # 만약 dp[i] 값이 order값과 같다면
        subsequence.append(input_array[i])  # 해당 input_array[i]값을 추가
        order -= 1  # 해당 order 값을 1씩 감소시킨다.

subsequence.reverse()  # 큰수부터 작은수로 뽑았기 때문에
print(*subsequence) #정답수열 출력