(Python/🥈2)백준리즘알고리즘 11722번: 가장 긴 감소하는 부분 수열

 

문제 바로가기 

문제:

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} 이고, 길이는 3이다.

입력:

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

 

출력:

첫째 줄에 수열 A의 가장 긴 감소하는 부분 수열의 길이를 출력한다.

 

import sys

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

n = int(input())
lst = list(map(int, sys.stdin.readline().split(" ")))

# 자기 자신만 선택했을 경우 1로 dp 최신화
dp = [1 for _ in range(n)]

# 총 길이
for i in range(n):
    # 앞에서 부터 그 길이까지
    for j in range(i):
        # 만약에 감소한다 ?
        if lst[i] < lst[j]:
            # 그러면 dp의 값을 최댓값으로 바꿔줌.
            dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))

 

LIS 알고리즘 이다

 

https://windy7271.tistory.com/entry/LIS-%EC%B5%9C%EC%9E%A5%EC%A6%9D%EA%B0%80%EC%88%98%EC%97%B4

LIS 최장증가수열