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

n = int(input())

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

dp = [1]*n

for i in range(n):
    for j in range(i):
        if array[i] > array[j]:
            dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))

이번 문제는 주어진 수열에서, 증가하는 부분 수열 중에 가장 긴 부분 수열을 구하는 문제이다.

 

처음 이 문제를 풀 때는 값이 증가하는 경우와 값이 감소하는 경우를 나눠서 풀었었는데, 결국 틀리는 경우의 수가 많아서 이 방법은 포기하기로 하였다.

그래서 다른 분의 풀이를 참고해본 결과, 이 문제를 풀기 위한 핵심 아이디어는 다음과 같다.

 

먼저 초기에 모든 수들이 각자 가지는 길이는 1이므로 1차원 리스트를 1로 선언 및 초기화 한 후에,

이중 반복문을 돌면서 만약에 현재 값이 앞의 값보다 큰 경우, 이전까지의 부분 수열의 길이의 최대 값에 1을 더한 값(dp[j]+1)과 현재 값(dp[i])를 비교하여 최대 값을 최신화해주는 방식으로 풀이한다.

 

간단하지만 중요한 LIS(Longest Increasing Subsequence)알고리즘을 이해할 수 있었던 좋은 문제였다 :)