[PS] BOJ 14002 / 가장 긴 증가하는 부분 수열 4

Minjun Kim

18 Jun 2025 • 3 min read

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

Thumbnail: Photo by Mayer Tawfik (Unsplash)

기본적인 풀이는 가장 긴 증가하는 부분 수열 2, 3과 동일합니다. 하지만, 이번 문제는 찾은 부분 수열의 원소들도 출력해야 합니다.

풀이

이분 탐색을 활용해 LIS 찾기

가장 긴 증가하는 부분 수열 2(BOJ 12015)의 풀이를 참고해주세요!

부분 수열의 원소 찾기

이제 부분 수열의 원소를 찾아야 합니다. 이는 이분 탐색을 통해 LIS의 길이를 계산하던 과정과 같이 진행할 수 있습니다.

먼저, 입력 받은 수열의 각 원소가 LIS의 몇 번째 원소가 되는지를 저장할 record 배열을 정의합니다.

record = [0 for _ in range(N)]
record[0] = 1

record 배열 정의

이제, record배열을 채워야 합니다. 앞서 이분탐색으로 LIS의 길이를 계산하던 반복문을 수정해봅시다.

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

LIS의 길이를 계산하던 반복문에서 record 배열도 같이 채운다!

lis배열에 원소를 채울 때, 해당 원소가 채워진 위치를 record배열에 기록하면 됩니다. 저는 편의상 실제 인덱스보다 1 증가시켜서 기록했습니다. (LIS의 길이와 맞추기 위해서입니다.)

이후, record배열을 역순으로 반복하며 실제 LIS의 원소를 구성하면 됩니다. 이는 LIS의 마지막 원소가 첫 원소에 비해 항상 record의 끝 쪽에 가깝게 위치하기 때문입니다.

lis_result = [0 for _ in range(j + 1)]
idx = j + 1
i = N - 1
while idx > 0 and i >= 0:
    if record[i] == idx:
        lis_result[j + 1 - idx] = A[i]
        idx -= 1
    i -= 1
print(j + 1)             # LIS의 길이 출력
print(*lis_result[::-1]) # LIS의 원소 출력

LIS의 원소 출력하기

전체 코드

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

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]
        record[i] = j + 1
    else:   # 그렇지 않다면, 이번 원소를 lis의 어디에 넣을지 이분탐색으로 결정한다.
        idx = binary_search(0, j, A[i])
        lis[idx] = A[i]
        record[i] = idx + 1

lis_result = [0 for _ in range(j + 1)]
idx = j + 1
i = N - 1
while idx > 0 and i >= 0:
    if record[i] == idx:
        lis_result[j + 1 - idx] = A[i]
        idx -= 1
    i -= 1
print(j + 1)
print(*lis_result[::-1])

solution.py