[Python] 백준11053 가장 긴 증가하는 부분 수열

17 Feb 2023 in Study on Algorithm

백준11053 가장 긴 증가하는 부분 수열 링크

문제

예제 입력

---

코드

import sys
n = int(input())
arr = list(map(int, sys.stdin.readline().split()))

# dp알고리즘
dp = [0] * n
for i in range(n):
    for j in range(i):
        # arr[i]보다 앞에 있는 값을 확인하고 거기까지의 최장 길이 확인
        if arr[j] < arr[i] and dp[i] < dp[j]:
            dp[i] = dp[j]
    # i번일 때 그 앞까지의 최장 길이 + 1(자기 자신 = i)
    dp[i] += 1

print(max(dp))

설명

파이썬을 통해서 사용자로부터 입력받아 dp알고리즘을 사용하여 가장 긴 증가하는 부분 수열(LIS-최장 부분 수열)를 구현했습니다.

---

결과