[다이나믹 프로그래밍] 11722번 - 가장 긴 감소하는 부분 수열

[백준] 11722번 - 가장 긴 감소하는 부분 수열

(한줄평) LIS 알고리즘을 알면 쉽게 풀 수 있었던 문제!

유사 문제: 11053, 11054

https://hseungyeon.tistory.com/304

[다이나믹 프로그래밍] ▲ 11053번 - 가장 긴 증가하는 부분 수열

https://hseungyeon.tistory.com/305

[다이나믹 프로그래밍] 11054번 - 가장 긴 바이토닉 부분 수열

 

풀이 시간: 5~10분 이내

1) 문제 해결 아이디어

1이상 1000이하의 크기인 수열 A가 주어졌을 떄 수열 A의 가장 긴 감소하는 부분 수열의 길이를 구하는 문제다. 11053번 가장 긴 증가하는 부분 수열의 길이를 구하는 문제에서 조건을 반대로 설정해주면 된다.

 

<점화식>

2) 소스코드

import sys
input = sys.stdin.readline

n = int(input())  # 수열 크기(1이상 1000이하 자연수)
graph = list(map(int, input().split()))  # 크기 n인 수열
d = [1] * n
for i in range(1, n):
  for j in range(i):
    # i번째 값보다 큰 수에서 최댓값 갱신
    if graph[j] > graph[i]:
      d[i] = max(d[i], d[j] + 1)
print(max(d))