[BOJ:11053] 가장 긴 증가하는 부분 수열

Link : https://www.acmicpc.net/problem/11053

Note

Dynamic Programming(이하 DP)의 개념을 익히기 위해서 풀어 본 문제다. DP는 기본적으로 작은 단위의 부분 문제들의 해를 구하고 이 부분 문제들을 이용해서 조금 더 큰 문제를 해결하고, 최종적으로는 최초 주어진 문제를 해결하는 알고리즘이다. 우리말로 동적 계획법으로도 불리는데 여기서 계획은 문제를 해결하는 과정에서 부분 문제들의 해를 기록해두면서 테이블을 채워가는 것을 의미한다.

가장 긴 증가하는 부분 수열 문제는 대표적인 DP문제이다. 수열이 주어지고, 수열의 부분집합에서 수들이 증가하는 값들로만 이루어진 부분집합의 크기를 구하는 문제이다. 예를 들어 문제에 주어진 예시 처럼 2, 7, 5, 8, 6, 4, 7, 12, 3라는 수열이 있을 때 2 5 6 7 12로 부분집합을 만들 수 있고, 이때 부분집합의 크기, 즉 수열의 길이가 5로 가장 크다.

DP로 사고하여 문제를 해결해보자. 먼저 작은 부분 문제를 해결한다. 여기서 작은 부분 문제는 문제의 주어진 수열을 작게 만드는 것이다.

2라는 수 하나만 있을 경우 증가하는 가장 긴 부분 수열의 길이는 1이다. 다시 하나 늘려서 2 7이라는 수열이 있을 때 가장 긴 부분 수열의 길이는 2(2, 7)이다. 다시 수를 하나 늘려서 2 7 5라는 수열이 있을 때를 생각해보면, 가장 긴 부분 수열의 길이는 2(2, 5)이다.

지금 처럼 계속 해서 수를 하나씩 늘려 가면서 생각해 볼 것이다. '2 7 5 8'이라는 수열에서는 '2 7 8', '2 5 8' 이 가장 긴 부분수열이다.

이때 8을 마지막 수라고 생각해서 수열을 만든 과정을 다시 살펴보자. 8보다 앞에 위치한 수들 중에서 8보다 작은 수 뒤에 8을 붙이면 증가하는 수열을 만들 수 있는데, 우리에게 필요한 것은 수열의 길이가 필요하기 때문에 수열을 만들기 보다는 수열의 길이만 생각하면 된다. 즉 7까지 만든 수열의 길이가 2였고, 8을 붙이면 길이가 3인 증가하는 수열을 만들 수 있고, 5까지 수열의 길이가 2였고 역시 8을 붙이면 길이가 3인 증가하는 수열을 만들 수 있다.

위에서 부터 수열의 수를 하니씩 늘려보면서 가장 긴 부분 수열의 길이를 구하는 생각 패턴을 찾았는데 문제에서 주어진 수열에서 인덱스 길이를 하나씩 늘리면서 추가한 수가 수열의 마지막에 오는 수열의 수라고 생각하고, 앞의 수들 중에서 마지막 수 보다 작은 수 뒤에 마지막 수를 붙이는 방식으로 생각하면 증가하는 수열을 만들 수 있다는 것을 알았다.

2 7 5 8 6 4 7 이라는 수열이 있을 때 7이 마지막 수라면 4뒤에 6뒤에 붙일 수 있고, 5뒤에 붙일 수 있고, 2뒤에도 붙일 수 있다. 2 4 7, 2 5 6 7, 2 5 7이 앞에서 말한 규칙대로 만든 수열이다. 이때 중요한 것은 가장 긴 수열 뒤에만 붙이면 된다. 6이 7보다 작은 수 중에 가장 긴 증가하는 수열을 만들 수 있는 마지막 수이다.

기본적인 DP방식으로 문제를 해결하는 것을 알아 보았다. 최초의 주어진 수열로 바로 가장 긴 증가하는 부분 수열을 구하기 보다는 수열의 범위를 좁힌 상태에서 먼저 가장 긴 증가하는 부분 수열을 구해본다. 부분 문제를 해결한 후에는 다시 수열의 범위를 조금씩 넓히면서 문제의 규칙을 발견한다. 그리고 앞에서 구한 해들을 이용할 방법은 없는지 생각해본다. 위 문제에서는 수열의 범위를 좁힌 상태에서 가장 긴 증가하는 부분 수열을 구하고 다시 늘린 수열에서 마지막 수보다 작은 수를 마지막 수라고 생각했을 때 구한 가장 긴 증가하는 부분수열의 길이를 이용했다.

Code

import sys

input = sys.stdin.readline
n = int(input())
arr = [0]
arr.extend(map(int,input().split()))

answer = 0
dy_LIS = [1]*(n+1)
for i in range(2,n+1):
    max_len = 1
    for j in range(i-1,0,-1):
        if arr[i] > arr[j]: #나(j)보다 작은 수 중에서 부분 증가 수열 길이가 가장 긴 값
            if max_len < dy_LIS[j]+1:
                max_len = dy_LIS[j]+1
            if answer == dy_LIS[j]:
                break
    dy_LIS[i] = max_len
    if answer < dy_LIS[i]:
        answer = dy_LIS[i]

print(answer)