https://www.acmicpc.net/problem/11722
11722번: 가장 긴 감소하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}
www.acmicpc.net
11053번(https://www.acmicpc.net/problem/11053)
가장 긴 증가하는 부분 수열의 문제에서 반대로 생각하면 된다.
증가하는 부분수열 문제에서는
현재 인덱스 값(array[i])이 앞의 인덱스(array[j])의 값보다 클 때(array[i] > arary[j]) DP값을 증가시켰다면,
감소하는 부분 수열 문제에서는
현재 인덱스 값 보다 앞의 인덱스 값이 클 때(array[i] < array[j]) DP값을 증가시켰다.
n = int(input())
dp = [1] * n
array = list(map(int, input().split()))
for i in range(n):
for j in range(i):
if array[i]<array[j] and dp[i]<=dp[j]:
dp[i] += 1
print(max(dp))
증가 부분 수열 문제를 풀었기에 쉽게 해결하긴 했지만,
여전히 완벽하게 숙지되지 않아 계획한 로드맵을 다 풀고 나서 다시 복습해야겠다고 생각했다.
'알고리즘 > Python' 카테고리의 다른 글
[백준/Python] 1912 연속합 (0) | 2022.01.18 |
---|---|
[백준/Python] 11054 가장 긴 바이토닉 부분 수열 (0) | 2022.01.18 |
[백준/Python] 11055 가장 큰 증가 부분 수열 (0) | 2022.01.18 |
[백준/Python] 11053 가장 긴 증가하는 부분 수열(LIS) (0) | 2022.01.18 |
[백준/Python] 2156 포도주 시식 (0) | 2022.01.17 |