[백준]11053번 가장 긴 증가하는 부분 수열 - DP

 

n = int(input())

num = list(map(int, input().split()))

length = [0] * n
for i in range(n):
    length[i] = 1
    for j in range(i):
        if num[j] < num[i]:
            length[i] = max(length[i], length[j] + 1)

print(max(length))

 

 코드 설명 

LIS 알고리즘을 구현하는 문제이다. 부분 수열의 길이를 저장하는 length 리스트를 [0] * n 의 길이만큼 초기화 한다.

반복문 안에서 기본길이는 1로 만들어 준다. i 번째 전에 존재하는 값들 중에 i 번째의 값보다 큰 수가 존재할 경우에는 현재 i 번째의 수열 길이와 j + 1 의 수열 길이중 큰 값으로 업데이트한다.

length 리스트에 저장된 값중 가장 큰 값을 출력한다.

 

Point : 카운트를 위해 기본적으로 길이는 1로 시작한다. 그 후 내부 반복문에서 현재의 값이 이전 값보다 크다면 현재 수열의 길이와 이전 수의 수열 길이 + 1을 비교하여 큰걸로 업데이트 하여 준다.

(length[i] 의 길이가 더 긴 경우도 있으므로 max 연산을 해주어야 한다)