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

문제 링크

문제링크

첫 번째 풀이

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}

단, 이 문제의 경우 dp = [-1e9-1]로 초기화하고 시작해야 합니다.

정답 코드

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 = [-1e9-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()))

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

두 번째 풀이

같은 방법을 적용하되, dp=[0]로 시작하고, 모든 x에 1e9를 더해줍니다. 1e9를 더해도 20억이기 때문에 c의 int 자료형에도 들어옵니다. 더하는 시간이 있어서 수행시간은 조금 더 늘어나네요!

정답 코드

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:
    x += 1e9
    if dp[-1] < x:
        dp.append(x)
    else:
        idx = bisect_left(dp, x)
        dp[idx] = x
print(len(dp)-1)

Success Notice: 수고하셨습니다.