[BOJ 11053] 가장 긴 증가하는 부분 수열 (Python)

풀이

LIS (Longest Increasing Subsequence) 라는 유명한 DP 문제이다.

처음에는 수열의 맨 왼쪽의 값을 현재값으로 지정하고 현재보다 큰 값이면 정답 배열에 추가하여 배열의 길이를 반환하는 방식으로 접근했다. 그러나 이렇게 풀게되면 틀리게 된다. 아래의 반례를 보자.

{10, 21, 1, 10, 20, 30, 40, 50, 60}

위 반례에서 가장 긴 증가하는 부분 수열은 {10, 21, 1, 10, 20, 30, 40, 50, 60}로 길이가 7이다. 반면에 처음 접근했던 방식으로 풀게되면 {10, 21, 1, 10, 20, 30, 40, 50, 60}로 길이가 6이 된다. 전체 수열 안에서 만들 수 있는 가장 긴 증가하는 부분 수열을 만들지 못하고 맨 왼쪽의 값을 기준으로 증가하는 부분 수열 하나만 만들게 되어 오류가 발생한다.

문제의 포인트는 자신을 포함하여 만들 수 있는 가장 긴 증가하는 부분 수열의 길이를 저장하는 것이다. 아래 그림을 통해 이해해보자.

코드

import sys

input = sys.stdin.readline
seq_size = int(input())
sequence = list(map(int, input().split()))

# 현재 자신을 포함하여 만들 수 있는 LIS 길이 저장
# (자기 자신을 포함하므로 dp 리스트 1로 초기화)
dp = [1] * seq_size

# i를 기준으로
for i in range(seq_size):
    # i보다 인덱스가 작은 모든 원소들 전부 탐색
    for j in range(i):
        # LIS 만들기
        if sequence[i] > sequence[j]:
            dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))

참고 : 링크