[백준 BOJ] 11722 가장 긴 감소하는 부분 수열 (Python)

11722번: 가장 긴 감소하는 부분 수열 (acmicpc.net)

11722번: 가장 긴 감소하는 부분 수열

다이나믹 프로그래밍 문제이다.

두 가지 방식으로 풀 수 있다.

1. 이중 for문: 현재 인덱스와 그 앞에 있는 모든 수를 비교한다. O(N^2)
2. bisect 사용: 반복문 안에서 이진탐색을 수행한다. O(NlogN)

1. dp 배열에 현재 수를 포함해 만들 수 있는 수열의 길이를 저장한다. 앞에 있는 어떤 수가 현재 수 보다 크면, 그 인덱스에 저장돼 있는 수열의 길이 + 1을 하여 저장한다. 이때 앞쪽 인덱스에 더 긴 경우가 있었을 수도 있기 때문에, max로 갱신해준다.

n = int(input())
a = list(map(int, input().split()))

dp = [1] * n

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

print(max(dp))

2. dp에 만들어진 수열의 원소를 저장하고, 가장 마지막에 저장된 원소를 기준으로 비교한다. 현재 수가 수열의 가장 마지막 수보다 작으면 수열의 끝에 저장한다. 그렇지 않을 때는 bisect를 통해 들어갈 위치를 찾아 저장한다.

bisect는 오름차로 정렬된 배열에서 위치를 찾기 때문에, 이 문제에서는 -1를 곱해 음수로 만들어 진행했다.

from bisect import bisect_left

n = int(input())
a = list(map(lambda x: int(x) * -1, input().split()))

dp = [a[0]]

for i in range(n):
    if a[i] > dp[-1]:
        dp.append(a[i])
    else:
        idx = bisect_left(dp, a[i])
        dp[idx] = a[i]

print(len(dp))