문제

[백준] 가장 긴 증가하는 부분 수열 2 (Gold 2)

요약

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하라. 단, A의 크기 N은 1보다 크고 1,000,000보다 작음.

분류

  • 다이나믹 프로그래밍

풀이

1. 내 풀이 (DP)

N의 크기가 크기 때문에 O(NlogN)에 해결해야 한다. 기본적인 아이디어는 다음과 같다.

  • dp[i]는 arr[i]가 포함된다고 했을 때, 가장 긴 증가하는 부분 수열의 길이를 말한다.
  • d[i]에는 가장 긴 증가하는 부분 수열의 i번째에 올 수 있는 가장 작은 수를 기록한다.


아래와 같은 과정을 통해 답을 도출할 수 있다.

  1. d에서 arr[i]보다 큰 수 중 가장 작은 수를 이진 탐색으로 찾는다.
    1. 만약 그 수가 d에서 가장 큰 수라면, d에 해당 수를 PUSH한다. dp[i]를 갱신한다.
    2. 만약 그 수가 d에서 가장 작은 수라면, d의 첫 번째 숫자를 갱신한다. dp[i] 갱신한다.
    3. 나머지 경우
      • 만약 d의 숫자와 arr[i]가 같다면, dp[i]만 갱신한다.
      • 만약 d의 숫자와 arr[i]가 다르다면, 더 작은 것으로 d의 숫자를 갱신한다. 그리고 dp[i]를 갱신한다.
  2. 해당 과정을 반복해 수열을 순회하고 가장 긴 부분 수열의 길이를 출력한다.


from bisect import bisect_left as bl

n = int(input())
arr = [0] + list(map(int, input().split()))

dp = [0] * (n + 1)
d = [0]

for i in range(1, n + 1):
    idx = bl(d, arr[i])
    if idx == len(d):
        d.append(arr[i])
        dp[i] = idx
    elif idx == 0:
        d[0] = arr[i]
        dp[i] = 1
    else:
        if d[idx] == arr[i]:
            dp[i] = idx
        else:
            d[idx] = min(d[idx], arr[i])
            dp[i] = idx

print(max(dp))