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

출처 : 백준, https://www.acmicpc.net/problem/11722

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

 

---

 

풀이

 

def solution(n, num_list):
    # 이전에 있는 것들 중 나보다 크면서 최대 길이가 가장 큰 것

    dp = [1 for _ in range(n)]

    for i in range(1, n):
        # 나보다 작은 idx 중에
        # 가장 긴 길이를 찾아서 + 1
        for j in range(i):
            if num_list[j] > num_list[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

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

print(solution(n, num_list))

 

---

 

Github

GitHub - bh2980/Algorithm-Problem: 알고리즘 풀이 흔적들