동캄의 코딩도장

백준 11722 [가장 긴 감소하는 부분 수열] 파이썬 본문

코테/BOJ

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

동 캄 2022. 2. 10. 15:10
반응형

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

import sys
input = sys.stdin.readline
N = int(input())
lst = list(map(int, input().split()))
lst.reverse()
dp = [1]*(N)

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

print(max(dp))

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

반응형

'코테 > BOJ' 카테고리의 다른 글

백준 11047 [동전 0] 파이썬  (0) 2022.02.10
백준 1439 [뒤집기] 파이썬  (0) 2022.02.10
백준 11055 [가장 큰 증가 부분 수열] 파이썬  (0) 2022.02.10
백준 9465 [스티커] 파이썬  (0) 2022.02.10
백준 11057 [오르막 수] 파이썬  (0) 2022.02.09
'코테/BOJ' Related Articles more