[백준 11722] 가장 긴 감소하는 부분 수열- python (solved.ac - 실버 2)

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

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

풀이

문제를 보았을때 알수있는 힌트

dp 문제로 처음을 1을 가지고 있는 dp를 만들고 이어서 자기자신보다 큰 값이 나오면 +1 하고 dp의 위치와 비교하여 큰 값을 입력하는 형식으로 풀면 쉽게 풀린다.

 

import sys

input= sys.stdin.readline

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

result=[]
dp=[1 for _ in range(n)]

n_list.reverse()

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

print(max(dp))

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/baekjoon11722.py

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리