[BOJ][Python][골4][14002] 가장 긴 증가하는 부분 수열 4

문제 링크

문제링크

가장 긴 증가하는 부분 수열 4과 가장 긴 증가하는 부분 수열 5는 같은 풀이방법과 코드를 사용합니다. 가장 긴 증가하는 부분 수열 5를 기준으로 설명합니다.

첫 번째 풀이

LIS 길이 구하기

dp[i] : arr[i]를 가장 큰 수로 가지는 가장 긴 감소하는 부분 수열의 길이

짧은 LIS는 $O(n^2)$입니다. 하지만 N이 큰 경우 이분탐색을 사용해서 O(nlogn)으로 진행합니다.

입력받은 수는 arr에 저장합니다. 그리고 dp = [0]를 준비합니다. arr에 들어있는 수 x에 대해 아래의 과정을 반복해서 진행합니다.

1. x가 dp의 마지막 값보다 크면 append합니다.
2. 아니라면 dp에서 x보다 큰 가장 작은 값의 index(bisect_left)를 찾습니다. 그 위치의 값을 x로 덮어씁니다.

3
10 5 20 을 입력받으면

1. {0}
2. {0, 10}
3. {0, 10}에서 5가 들어갈 idx 1을 찾아 {0,5}로 대체
4. {0,5,20}

5
10 50 20 30 40 을 입력받으면

1. {0}
2. {0,10}
3. {0,10, 50}
4. {0,10, 50} 에서 20이 들어갈 idx 3을 찾아 {0,10,20}으로 대체
5. {0,10, 20, 30}
6. {0,10, 20, 30, 40}

LIS 자체를 구하기

이 문제는 LIS 길이뿐만 아니라, LIS 자체를 요구합니다. 일반적으로 추적은 대부분 인덱스를 활용한다.를 기억하고 설명을 시작하겠습니다. 아래의 설명에서만큼은 {}가 list를 의미한다고 이해해주세요. 정리하다보니 {}로 적어버렸네요.

길이를 구하는 방법만으로는 LIS 자체를 구할 수 없습니다. 예를 들어 1 5 10까지만 보면 LIST는 {1,5,10}입니다. 1 5 10 4 6까지만 보면 LIS는 {1,5,10},{1,4,6} 두 가지 경우가 있지만 후자가 LIS가 더 길어질 수 있도록 가능성을 열어둡니다. 1 5 10 4 6 7이나 1 5 10 4 6 11이 오는 경우 모두 LIS를 길이 4로 구할 수 있습니다. 하지만 1 5 10 4까지만 보고 LIS를 출력한다면 {1,4,10}이 출력되는 문제가 있습니다.

이러한 경우 LIS의 길이뿐만 아니라 LIS를 출력해야하는 경우 index를 활용한 추적을 사용합니다. 위에서 설명한 방법대로 {}에 하나의 값을 추가하는 것은 동일합니다. 하지만 값을 추가할 때 값이 추가된 idx를 같이 기록합니다.

추가되는 값은 (insert되는 index, value)의 형태로 {}에 추가됩니다.

추가된 값	LIS상태	tracking 상태
10	{10}	{ (0,10) }
20	{10, 20}	{ (0,10), (1,20) }
10	{10, 20}	{ (0,10), (1,20), (0,10) }
30	{10, 20,30}	{ (0,10), (1,20), (0,10), (2,30) }
20	{10, 20,30}	{ (0,10), (1,20), (0,10), (2,30), (1,20) }
50	{10, 20, 30, 50}	{ (0,10), (1,20), (0,10), (2,30), (1,20), (3,50) }

LIS는 길이가 4이고 마지막 index가 3인 것을 알 수 있습니다. 이 3이라는 값을 통해, 가장 마지막 tracking 상태의 (index,value)의 index가 3부터 0까지인 value를 출력하면 LIS 자체의 역순을 구할 수 있습니다. 출력하는 부분은 코드로 이해하시는 것이 더 편하겠습니다.

정답 코드

import sys
from math import sqrt, ceil
from bisect import bisect_left, bisect_right
import copy

# sys.stdin = open("input.txt", "r")

n = int(input())
# R, C, K = 1, n, 1
# dp = [[0] * C for _ in range(R)]
# dp = [[[0] * K for _ in range(C)] for _ in range(R)]
# MOD = 1000000000
arr = list(map(int, sys.stdin.readline().split()))
dp = [arr[0]]  # LIS의 길이를 찾기 위한 배열
tracking = [(0, arr[0])]  # LIS를 찾기 위한 (index, value) List
arr = arr[1:]
LIS_length = 1

for x in arr:
    if dp[-1] < x:
        dp.append(x)
        tracking.append((LIS_length, x))
        LIS_length += 1
    else:
        idx = bisect_left(dp, x)
        dp[idx] = x
        tracking.append((idx, x))

ans = []  # 출력을 위한 stack
LIS_length -= 1
for x in reversed(tracking):
    if x[0] == LIS_length:
        ans.append(x[1])
        LIS_length -= 1

print(len(dp))
print(*reversed(ans), sep=' ')

Success Notice: 수고하셨습니다.