BOJ 11722번 : 가장 긴 감소하는 부분 수열 (Python/Silver 2)

11722번: 가장 긴 감소하는 부분 수열

---

설명

부분 수열의 최대 길이를 구해야 하는 문제이다. 부분 수열이란 주어진 수열의 일부 항을 원래 순서대로 나열하여 얻을 수 있는 수열이다. 쉽게 말해서 이전 수보다 작으면 수열이 이루어진다. 흔히 수학에서 보았던 두 항의 차이가 일정한 등차수열을 말하는 것이 아니다. 

 

예를 들어, A : { 10, 30, 10, 20, 20, 10 } 이라는 수열이 있을 때, 부분 수열은 A : { 10, 30, 10, 20, 20, 10 } 이고, 최대 길이는 3이다.

 

풀이

가장 긴 증가하는 부분 수열 문제와 같은 문제이다.

풀이 ➜ https://dev-cloud.tistory.com/198

 

반복문을 돌려주면서 현재 값(i)이 이전 값(j)보다 작으면, dp에서의 현재 위치(i)와 이전 위치(j)에서 +1을 해준 카운트 값과 비교하여 더 큰 카운트 값을 현재 위치(i)에 저장해준다.

이렇게 하면 지금껏 카운트 했던 값 중 큰 값을 저장하면서 수열의 최댓값을 알 수 있는 것이다.

최종으로 결과를 출력할 때 dp에 저장되어 있는 값에서 최댓값을 출력한다.

 

Solution

#22:20 - 22:50

import sys
input = sys.stdin.readline

N = int(input())
dp = [1]*N
num = list(map(int, input().split()))

for i in range(N):
    for j in range(i):
        if num[i] < num[j]:
            dp[i] = max(dp[i], dp[j]+1)
print(max(dp))

---

👩‍💻 회고

이번 문제에서는, 작은 수를 찾아서 카운트 리스트에 현재 인덱스와 이전 인덱스 중 최댓값을 현재 인덱스에 다시 저장하는 방식으로 풀었다. 

 

가장 긴 증가하는 부분 수열 문제를 최근에 풀었는데도 한번에 구현하지 못했다. 아직 dp 문제를 어떻게 풀어야 할지 감이 잡히지 않은 것 같다.