[Python] BOJ / 12738번 / 가장 긴 증가하는 부분 수열 3

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

---

📝 풀이

• LIS 알고리즘 사용
  • DP 배열을 사용하여 구현할 경우 시간초과가 발생하므로 이분 탐색 알고리즘으로 구현
  • 다만 배열을 정렬하면 안 됨
• 배열을 따로 생성한 뒤 해당 배열에 오름차순으로 값을 순서대로 추가하여주는 식으로 구현
• 문제에서 물어보는 건 '가장 긴 증가하는 수열의 길이'이므로 수열의 값과 순서는 상관 없으며 우리는 result 배열의 가장 끝 요소(수열에서 현재까지 찾은 가장 큰 수)만 비교해가며 값을 추가해주면 된다.

---

💻 소스 코드

import sys

input = sys.stdin.readline

def binary_search(left, right, target):
    while left <= right:
        pivot = (left + right) // 2
        if result[pivot] == target:
            return pivot
        elif result[pivot] < target:
            left = pivot + 1
        else:
            right = pivot - 1

    return left

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

result = [arr[0]]
for i in range(1, n):
    if result[-1] < arr[i]:
        result.append(arr[i])
    else:
        idx = binary_search(0, len(result), arr[i])
        result[idx] = arr[i]

print(len(result))