[백준 11053] 가장 긴 증가하는 부분 수열 with Python

문제 링크

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

11053번: 가장 긴 증가하는 부분 수열

풀이

import sys

N = int(sys.stdin.readline())
seq = list(map(int, sys.stdin.readline().split()))
dp = [seq[0]]

def binary(dp, n):
    low = 0
    high = len(dp)-1
    while low <= high:
        mid = (low + high)//2
        if dp[mid] > n:
            high = mid - 1
        elif dp[mid] < n:
            low = mid + 1
        else:
            return mid

    return high+1

for i in seq:
    if i > dp[-1]:
        dp.append(i)
    else:
        dp[binary(dp, i)] = i

print(len(dp))

 

수열을 seq에 저장하고 seq을 순회하면서 dp의 가장 마지막 요소(dp의 최댓값)보다 크면 dp의 마지막에 추가하고, 그렇지 않다면 이분 탐색을 통해 오름차순으로 dp의 몇 번째 인덱스에 들어갈 수 있는지 찾아서 해당 인덱스의 요소를 현재 순회중인 seq의 요소 i로 대체한다. dp[i]는 수열의 (i+1)번째 숫자로 끝나는 부분 수열의 최대 길이이다.

 

seq = [1, 2, 1, 6, 4, 5]일 때,

1. 먼저 dp에 seq[0]이 이미 있기 때문에 seq의 첫 번째 수 1을 순회하고 난 뒤 dp는 [1]이다.

2. 2는 dp의 최댓값보다 크기 때문에 dp는 [1, 2]가 된다.

3. 1은 이미 있는 수이기 때문에 dp는 변하지 않는다. (binary(dp, 1)이 0을 반환하므로)

4. 6은 dp의 최댓값보다 크기 때문에 dp는 [1, 2, 6]이 된다.

5. 4는 2와 6 사이에 위치하므로, 6을 대체하여 dp는 [1, 2, 4]가 된다.

6. 5는 dp의 최댓값보다 크기 때문에 dp는 [1, 2, 4, 5]가 된다.