[김태원 알고리즘] 최대 부분 증가수열 (LIS: Longest Increasing Subsequence) (DP)

사용 언어: Python3

문제

풀이

Bottom-Up

N = int(input())
lst = list(map(int, input().split())) # 숫자를 담아놓을 리스트
length = [0] * N # lst의 각 숫자가 마지막 원소라고 가정했을 때의 길이를 담아놓을 리스트
length[0] = 1 # 첫 번째 원소가 마지막 원소라면 무조건 길이 1

for i in range(1, N):
    mx = 0
    for j in range(i): # ✅ 내(lst[i]) 앞의 원소들을 탐색
        if lst[j] < lst[i]: # ✅ 나보다 값이 작아야 한다 (증가수열을 만들어야 하기 때문)
            mx = max(length[j], mx)
    length[i] = mx + 1 # ✅ 나(lst[i])까지 뒤에 붙는거니까 +1

print(max(length))

• 성공!

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기