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

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

 

수열 A가 주어졌을 때,

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

 

import sys

input = sys.stdin.readline

N = int(input())
card = list(map(int, input().split())) # 수열 입력받기
LIS = [[] for _ in range(N)] # 증가하는 수열의 길이를 저장할 배열

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

    LIS[i] = [card[i]] # 초기값 세팅
    
    for j in range(i):
  
        if(card[j] < card[i]): # 작은 값이 있을 시
            if(len(LIS[i]) < len(LIS[j])+1): # 증가하는 수열이 더 길 때
                LIS[i] = LIS[j].copy() # 이전 증가하는 수열 값 가져오기
                LIS[i].append(card[i]) # 현재 수열값 추가

max_length_list = max(LIS, key=len) # LIS 찾기
max_length = len(max_length_list) # LIS 길이 계산

print(max_length) # LIS 길이 출력
print(' '.join(map(str, max_length_list))) # LIS 출력

 

 

 

[문제풀이]

---

 

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

 

 

 

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

 

 

 

이렇게 구해낸 각 수열의 증가하는 수열의 배열 중 가장 긴 길이를 갖는 수열을 찾으면 LIS다!