반응형
Notice
Recent Posts
Recent Comments
Link
동캄의 코딩도장
백준 11722 [가장 긴 감소하는 부분 수열] 파이썬 본문
반응형
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 |