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

문제 : https://www.acmicpc.net/problem/11053

 

수열 A가 주어졌을 때,

가장 긴 증가하는 부분 수열의 길이를 구하는 문제다.

 

import sys

input = sys.stdin.readline

N = int(input())
card = list(map(int, input().split())) # 수열 입력받기
length = [0]*(N) # 수열의 길이를 저장할 배열

# DP 테이블 생성
for i in range(N):

    length[i] = 1 
    
    for j in range(i):
  
        if(card[j] < card[i]):
            length[i] = max(length[i], length[j]+1)

print(max(length))

 

 

[문제풀이]

---

 

이 문제는 동적 계획법, 즉 DP를 이용해서 풀 수 있다.

 

 

 

각 수열마다 증가하는 수열의 길이를 메모이제이션해나가며 문제를 푼다.

 

 

이렇게 구해낸 증가하는 수열의 값 배열 중 가장 큰 값을 찾으면 LIS, 가장 큰 증가하는 수열의 길이값을 구할 수 있다!