작은 지식주머니
백준 파이썬 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
n=int(input())
s=list(map(int,input().split()))
dp=[1]*n
for i in range(1,n):
for j in range(i):
if s[i] < s[j]:
dp[i] = max(dp[i],dp[j]+1)
print(max(dp))dp중 간단한 문제라고한다. 난 아니었는데..
s[0],s[1]를 예시로 감소하지 않는 수이므로 if문의 조건에 맞지 않다.
s[1],s[2]를 예시로 30 , 10 이므로 감소하기때문에 max(dp[1],dp[2]+1)의 조건이 발동되어 [1,1,2,1,1,1]이 된다.
이렇게 반복하면 [1,1,2,2,2,3] 의 결과가 나오기떄문에 max(dp)를 출력하면 된다.
'백준 python 기록' 카테고리의 다른 글
| 백준 파이썬 1931 회의실 배정 (0) | 2021.09.15 |
|---|---|
| 백준 1912 파이썬 연속합 (0) | 2021.09.14 |
| 백준 15469 파이썬 N과 M(1) (0) | 2021.09.12 |
| 백준 11053 파이썬 가장 긴 증가하는 부분 수열 (0) | 2021.09.12 |
| 11047 백준 파이썬 동전 0 (0) | 2021.09.11 |
'백준 python 기록' Related Articles
more
