[백준/BOJ] 12015 - 가장 긴 증가하는 부분 수열 2

12015 - 가장 긴 증가하는 부분 수열 2

📌 문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

📋 코드

import sys
from bisect import bisect_left

N = int(input())
num = list(map(int, input().split()))

dp = [num[0]]
for i in range(1, N):
    if dp[-1] < num[i]:
        dp.append(num[i])
    else:
        pos = bisect_left(dp, num[i])
        dp[pos] = num[i]

print(len(dp))

💡 한마디

가장 긴 증가하는 부분 수열 문제랑 같지만 동일한 알고리즘으로 풀면 시간 초과 난다. 11053번 문제는 입력이 1,000까지만 들어와 O(n²) 으로 풀이가 가능한 반면 이 문제는 1,000,000까지 들어온다.

고로 DP 테이블을 다음과 같이 구성했다.

• dp 리스트 맨 마지막 값보다 들어오는 값이 큰 경우
  • dp 리스트에 추가
• 그렇지 않은 경우
  • bisect_left를 이용하여 현재 값이 들어갈 수 있는 인덱스의 원래 값과 교체

이로써 시간복잡도 O(nlogn) 만에 풀 수 있지만 최종적으로 리스트에 들어있는 값들은 실제 LIS가 아니다. 단지 길이만 알 수 있다.

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