백준 14002 문제 풀이 python

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

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

DP 유형중 유명한 가장 긴 증가하는 부분 수열 문제 시리즈이다

✍ 나의 풀이

n = int(input())

arr = list(map(int,input().split()))

dp = [1] * n

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

dpmax = max(dp)

result = []
count = dpmax
dp = dp[::-1]
arr = arr[::-1]

while count > 0:
    for i in range(n):
        if dp[i] == count:
            result.append(arr[i])
            count -= 1

print(dpmax)
print(' '.join(map(str,result[::-1])))

깔끔하게 구현하고 싶어서 시간이 많이 들었는데 그렇게 마음에 들진 않았다..

---

🧠 문제 이해

n = int(input())

arr = list(map(int,input().split()))

dp = [1] * n
# 수열이 i까지 존재할때의 증가하는 부분수열의 길이 

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

print(max(dp))
# 증가하는 부분 수열의 길이중 최대값 출력

이렇게 하면 가장 긴 증가하는 부분수열의 "길이"를 구할 수 있다.
그러나 이번 문제에서는 가장 긴 증가하는 부분수열 또한 나타내어야한다.

이 문제는 스폐셜 저지 문제였다. 정답이 여러개 존재할 수 있다는 의미인데,

[3,4,1,2] 수열이 주어졌을때 가장 긴 증가하는 부분수열은
[3,4] 와 [1,2]로 나타낼 수 있다.

문제에서는 아무거나 하나만 출력하면 된다고 명시돼있다.

나는 나중에 등장하는 가장 긴 증가하는 부분수열을 출력하는 것이 바람직 하다고 생각했고,

dp테이블과 수열을 뒤집어서 하나씩 검사해서 count와 일치하면 출력할 수열에 append했다.

result = []		# 가장 긴 부분 수열 저장할 리스트
count = max(dp)	 	

dp = dp[::-1]
arr = arr[::-1]
# dp테이블과 입력받았던 수열을 뒤집음

while count > 0:
    for i in range(n):
        if dp[i] == count:
            result.append(arr[i])
            count -= 1
            
print(dpmax)
print(' '.join(map(str,result[::-1])))