[백준]11053번: 가장 긴 증가하는 부분 수열 / 11722번: 가장 긴 감소하는 부분 수열

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

11053번: 가장 긴 증가하는 부분 수열

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

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

---

이 문제 유명한 문제라고 한다

난 dp인거 알고 풀려고 해도 아이디어가 잘 떠오르지 않아서 막혔던 문제...

 

 

풀이

• 수열 A와 길이가 똑같은 배열 dp를 만든다.
• dp에는 수열의 특정원소가 마지막이 되는 경우 부분수열의 길이가 저장된다.
• 수열A를 순회하면서 해당 원소보다 앞에 위치하는 원소들을 하나씩 체크한다. (이중 for문 돌려야함)
  • 앞의 원소 값 < 현재 원소 값 을 만족하면(오름차순 조건),
  • 앞의 원소가 마지막 원소인 부분수열에 현재 원소를 추가했을 경우 길이가 최대가 된다면 현재 dp값을 갱신해준다.
  • 즉, A[i] > A[j] 를 만족하면서 DP[i] < DP[i]+1 인 경우 갱신해주면 된다. (i=현재 인덱스, j=비교하는 앞쪽 원소 인덱스)

 

가장 긴 감소하는 부분수열 문제 같은 경우는 두가지로 풀 수 있는데,

1. 부등호만 바꿔준다

2. .reverse() 함수를 통해 증가하는 부분수열문제로 바꾸어 풀어준다

 

#가장 긴 감소하는 부분 수열 문제

n = int(input())
arr = list(map(int,input().split()))


dp = [1]*n

for i in range(n):
  for j in range(0,i):
    if arr[i]<arr[j]:
      dp[i] = max(dp[i],dp[j]+1)

print(max(dp))