|
n = int(input())
l = list(map(int, input().split()))
order = [0 for i in range(n)]
for after in range(n) :
for before in range(after) :
if l[after] > l[before] and order[after] < order[before] :
order[after] = order[before]
order[after] = order[after] + 1
m = max(order)
print(m)
lis = []
for i in range(n) :
if order[n-1-i] == m :
lis.append(l[n-1-i])
m = m - 1
for i in range(len(lis)) :
print(lis[len(lis)-1-i], end = ' ')
|
부분수열의 길이를 출력하는건 11503과 같지만, 이번엔 그 수열 자체도 출력해야 한다.
이전 문제의 풀이과정에서 order를 저장한 리스트가 있으므로, 거기서 order = 1 ~ max인 원소를 뽑으면 될 것이다.
이때 리스트를 [0]부터 정방향으로 탐색하면 order = i 와 i+1이 같은 부분순열의 order라는 보장이 없다.
예를 들어 리스트가 [10 50 20 30]이면 order는 [1 2 2 3]이고, order 1 2 3을 뽑으면 [10 50 30]으로 잘못된 추출이다.
따라서 리스트의 역순으로 max부터 1까지 추출해야 하고, 이것을 뒤집으면 올바른 부분수열이 나온다.
(위의 예시에서 역순으로 3 2 1을 뽑으면 [30 20 10]이 추출되고 이를 뒤집으면 [10 20 30]이 된다.)
'Week 01 ~ 04 : 알고리즘 문제 풀이' 카테고리의 다른 글
| 파이썬 백준 1927 최소 힙 (0) | 2021.11.17 |
|---|---|
| 파이썬 백준 14003 가장 긴 증가하는 부분 수열 5 (0) | 2021.11.17 |
| 파이썬 백준 12738 가장 긴 증가하는 부분 수열 3 (0) | 2021.11.17 |
| 파이썬 백준 12015 가장 긴 증가하는 부분 수열 2 (0) | 2021.11.17 |
| 파이썬 백준 11722 가장 긴 감소하는 부분 수열 (0) | 2021.11.17 |