[백준] 11722 가장 긴 감소하는 부분 수열

문제

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} 이고, 길이는 3이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 $A_i$가 주어진다. (1 ≤ $A_i$ ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 감소하는 부분 수열의 길이를 출력한다.

내 풀이

import sys
input = sys.stdin.readline

n = int(input())
list1 = list(map(int,input().split()))

dp = [1] * n    # dp를 1로 초기화

for i in range(n):
    for j in range(0, i):
        if list1[i] < list1[j] :
            dp[i] = max(dp[i], dp[j]+1)

print(max(dp))

코멘트

리스트(수열)의 앞뒤 요소들을 비교해서 큰 것에서 작은 것 순서대로 새 리스트에 입력을 하면 되겠다고는 생각했는데 구체적으로 어떻게 구현해야할지 모르겠어서 다른 풀이를 참고하게 되었다. 이 문제는 동적 계획법을 이용해서 풀어야 하는 문제로, dp라는 리스트를 만들어 초기화해주고 여기에 특정 조건을 만족하면 뭔가 입력해주는 방식으로 풀이하는 유형이다. 따라서 이번 문제는 이중 반복문을 돌리면서 리스트의 앞뒤 요소들을 비교하고 내림차순의 순서대로 있다면 1씩 더해주어서 몇 개 요소까지 내림차순 수열을 만들 수 있는지 세면 되는 문제였다.
동적 계획법 유형 문제를 더 많이 풀고 감을 잡을 수 있도록 해야겠다.

References

https://www.acmicpc.net/problem/11722
https://velog.io/@gandi0330/Python-백준-가장-긴-감소하는-부분-수열-11722번-DP