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

DP 좋은 문제 추천

https://won-percent.tistory.com/entry/%EC%A2%8B%EC%9D%80-DP-%EB%AC%B8%EC%A0%9C%EB%93%A4-%EC%B6%94%EC%B2%9C

문제

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

풀이

a : [10, 30, 10, 20, 20, 10]

처음엔 if a[j] > a[i] : dp[i] = dp[j] + 1 로 풀었다. a[i] 보다 큰 것만 찾아서 +1 하다보니 맨 오른쪽 10의 경우, 20을 중복으로 더해서 원하는 답이 나오지 않았다.

이걸 어떻게 해결할까 고민하다가 max 로 풀긴했는데 손으로 일일히 for문을 돌려가면서 이해한거라 자존심 상한다. 아니 잘하는 사람들은 머리 속에서 다 돌아가려나? 곧 따라잡아드림!

n = int(input())
a = list(map(int,input().split()))
dp=[1 for _ in range(n)]
for i in range(n):
 for j in range(i):
 if a[j]>a[i]:
 dp[i] = max(dp[j]+1, dp[i])
print(max(dp))