백준/ Silver 2 문제 , 백준 파이썬 11722, 가장 긴 감소하는 부분 수열

백준/ Silver 2 문제 , 백준 파이썬 11722, 가장 긴 감소하는 부분 수열

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
오늘 배운 것을 이용하여 reverse로 돌려 똑같이 풀어봤다.

 

<문제 출처>

 

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

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

------------------------------------------------------------------------------------------------------------------------------

 

 

https://bmy1320.tistory.com/entry/%EB%B0%B1%EC%A4%80-Silver-2-%EB%AC%B8%EC%A0%9C-%EB%B0%B1%EC%A4%80-%ED%8C%8C%EC%9D%B4%EC%8D%AC-11053-%EA%B0%80%EC%9E%A5-%EA%B8%B4-%EC%A6%9D%EA%B0%80%ED%95%98%EB%8A%94-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4

백준/ Silver 2 문제 , 백준 파이썬 11053 , 가장 긴 증가하는 부분 수열

 

전에 풀었던 문제의 응용형이다. reverse() 만 추가하면 동일한 코드로 풀어낼 수 있다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

------------------------------------------------------------------------------------------------------------------------------

정답

 

 

 

 

 

 

 

import sys
input=sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))
A.reverse()
dp=[0 for _ in range(N)]

for i in range(N):
    for j in range(i):
        if A[i]>A[j] and dp[i]<dp[j]:
            dp[i]=dp[j]
    dp[i]+=1

print(max(dp))