[BOJ][Python][골2][12015] 가장 긴 증가하는 부분 수열 2

문제 링크

문제링크

첫 번째 풀이

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}

정답 코드

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]
# 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()))

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

Success Notice: 수고하셨습니다.