백준 14002번 가장 긴 증가하는 부분 수열 4 파이썬 풀이

Python

[Python] 백준 알고리즘 온라인 저지 14002 가장 긴 증가하는 부분 수열 4

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

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

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

수열을 받으면 그중 길이가 제일 긴 증가하는 수열을 구하는 문제이다. 11053번 문제와 유사하지만 그 수열까지 출력하여야 한다. 필자는 순서가 꼬여 이 문제부터 접하고 11053번을 풀게 되었다;;

---

소스코드

import sys
input = sys.stdin.readline

n = int(input())  
nums = list(map(int, input().split()))
dp = [1 for _ in range(n)]

# 길이 구하는 for문
for i in range(n):
  for j in range(i):
    if nums[i] > nums[j]:
      dp[i] = max(dp[i], dp[j]+1)

print(max(dp))

# 수열 출력을 위한 for문
max_dp = max(dp)
arr = []
for i in range(n-1, -1, -1):
  if dp[i] == max_dp:
    arr.append(nums[i])
    max_dp -= 1

arr.reverse()
for i in arr:
  print(i, end=" ")

---

풀이

1. 길이 구하기

증가하는 수열의 길이를 구하기 위해서는 nums 리스트를 돌며 자신보다 작은 수가 있는지 확인해야 한다.

dp에는 i가 수열의 최대일 때 길이를 저장한다.

 A = {10, 20, 10, 30, 20, 50}에서 i = 3 일 때 j를 통해 30보다 작은 수들을 찾는다 10, 20의 dp = [1, 2]이다 더 큰 dp에서 1을 더하여 저장하므로 수들을 비교하여 길이를 저장할 수 있다.

dp = [1, 1, 1, 1, 1, 1] -> [1, 2, 1, 3, 2, 4]

 

2. 수열 출력

dp를 통해 가장 긴 수열의 길이를 알고 있으므로 이를 이용하여 수열을 작성할 수 있다.

i가 1씩 감소하는 for문으로 작성하고 dp[i] = max_dp일 때의 인덱스 i를 이용, nums[i]를 arr[]에 추가하고 max_dp에서 1을 빼준다.

하지만 이런 방식으로 arr에 추가한다면 [4, 3, 2, 1] 순서로 출력되므로 리스트를 거꾸로 뒤집어주어야 한다.

reverse 내장 함수를 이용하고 arr를 띄어쓰기와 함께 출력하면 된다.

---

풀이 결과

14002 풀이 결과