문제 링크: https://www.acmicpc.net/problem/12015

Thumbnail: Photo by Imagine Buddy (Unsplash)

어제 풀었던 LIS 문제와 마찬가지이나, LIS의 길이가 아닌 원소 합을 기준으로 찾는 문제입니다.

풀이

LIS 이해하기

LIS(Longest Increasing Subsequence)에 대한 설명은 이전 글을 참고해주세요!

DP 풀이의 한계

이전까지는 입력으로 주어지는 배열의 길이가 1,000 정도로 작아 DP 방식으로도 충분히 풀 수 있었습니다. 하지만, 이번 문제는 배열의 길이가 1,000,000으로 \(O(N^2)\)의 시간 복잡도를 가지는 DP 방식으로는 풀 수 없습니다.

이분 탐색을 활용한 LIS 풀이

이분 탐색이 \(O(\log N)\)의 시간에 배열을 탐색한다는 점을 이용해 전체 풀이의 시간 복잡도를 \(O(N \log N)\)으로 개선할 수 있습니다.

이분 탐색 구현

이분 탐색과 매개변수 탐색에 대한 설명은 이전 글을 참고해주세요!
이번 풀이도 이분 탐색이라고 적었지만 실제로는 매개변수 탐색의 방식을 사용합니다.

아래 코드는 '조건을 만족하는 최솟값'을 탐색하는 매개변수 탐색 구문입니다. 여기서 사용된 조건은 '찾고자 하는 값(value)보다 크거나 같은가?' 이며, 최종적으로 탐색한 위치는 'value보다 크거나 같은 값이 위치하는 최소 위치'가 됩니다.

lis배열은 아래 문단에서 설명합니다!

def binary_search(left, right, value):
    while left < right:
        mid = (left + right) // 2
        if lis[mid] < value:
            left = mid + 1
        else:
            right = mid
    return right

이분 탐색을 활용해 LIS 찾기

이제 이분 탐색을 LIS를 찾는 과정에 활용해봅시다. 여기서는 lis라고 부르는 임의의 배열 하나를 더 사용합니다. 배열 lis는 '배열의 인덱스 \(i\)에 대해, 길이 \(i\)의 LIS의 마지막 원소로 올 수 있는 최솟값'을 저장합니다. 또, 정수형 변수 j는 현재 lis배열에 저장된 가장 마지막 원소의 위치(인덱스)를 기록합니다.

배열 lis는 0번 인덱스에 입력받은 배열의 첫 번째 원소를 초기값으로 저장합니다.
이후, 입력받은 배열의 원소들을 1부터 \(N-1\)까지 하나씩 순회하며 다음을 반복합니다:

• 현재 입력 배열의 원소(A[i])가 lis 배열의 마지막 원소(lis[j])보다 크다면, LIS의 길이를 1 증가시키고 현재 원소를 lis배열의 끝에 추가합니다.
• 그렇지 않다면, 현재 입력 배열의 원소(A[i])를 lis배열의 \(0 \dots j\) 사이에서 어디에 넣어야 하는지 이분탐색으로 찾습니다.
  • 이후 찾아낸 위치(idx)에 해당하는 lis배열의 원소를 현재 입력 배열의 원소로 덮어씁니다. (최솟값 갱신)

A = list(map(int, input().strip().split()))  # 입력 배열
lis = [0 for _ in range(N)]
lis[0] = A[0]
j = 0
for i in range(1, N):
    if A[i] > lis[j]: # 현재 LIS의 마지막 원소보다 이번 원소가 더 크다면
        j += 1
        lis[j] = A[i]
    else:   # 그렇지 않다면, 이번 원소를 D의 어디에 넣을지 이분탐색으로 결정한다.
        idx = binary_search(0, j, A[i])
        lis[idx] = A[i]

print(j + 1)

아래 과정을 그림으로 나타내면 다음과 같습니다.

사진 출처: hsayho.log

전체 코드

input = open(0).readline
N = int(input().strip())
A = list(map(int, input().strip().split()))
lis = [0 for _ in range(N)]
lis[0] = A[0]

def binary_search(left, right, value):
    while left < right:
        mid = (left + right) // 2
        if lis[mid] < value:
            left = mid + 1
        else:
            right = mid
    return right

j = 0
for i in range(1, N):
    if A[i] > lis[j]: # 현재 LIS의 마지막 원소보다 이번 원소가 더 크다면
        j += 1
        lis[j] = A[i]
    else:   # 그렇지 않다면, 이번 원소를 lis의 어디에 넣을지 이분탐색으로 결정한다.
        idx = binary_search(0, j, A[i])
        lis[idx] = A[i]


print(j + 1)