Softeer 징검다리 2 (난이도 4)

오답 코드 (DP, N^2, 시간 제한 초과)

import sys
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
dp = [1 for i in range(N)]
dpR = [1 for i in range(N)]

for i in range(1, N):
    r = N - i - 1
    for j in range(i):
        if A[j] < A[i] and dp[i] < dp[j] + 1:
            dp[i] = dp[j] + 1
    for j in range(N - 1, r, -1):
        if A[j] < A[r] and dpR[r] < dpR[j] + 1:
            dpR[r] = dpR[j] + 1

maxV = 0
for i in range(N):
    if maxV < dp[i] + dpR[i]:
        maxV = dp[i] + dpR[i]
print(maxV - 1)

정답 코드 (binary search, NlogN)

import sys
def bin_search(l, key, j):
    left, right, mid = 0, j, 0
    while left < right:
        mid = (left + right) // 2
        if l[mid] < key:
            left = mid + 1
        else:
            right = mid
    return right

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
ans = [0 for i in range(N)] # record the position of A's value
ansR = [0 for i in range(N)] # record the position of A's value
lis = [0 for i in range(N)] # record the LIS
lisR = [0 for i in range(N)] # record the LIS in reversed order

j = 0
ans[0], ansR[N - 1] = 1, 1
lis[0], lisR[0] = A[0], A[N - 1]
for i in range(1, N):
    if A[i] > lis[j]:
        j += 1
        lis[j] = A[i]
        ans[i] = j + 1
    else:
        idx = bin_search(lis, A[i], j)
        lis[idx] = A[i]
        ans[i] = idx + 1

j = 0
for i in range(N - 1, -1, -1):
    if A[i] > lisR[j]:
        j += 1
        lisR[j] = A[i]
        ansR[i] = j + 1
    else:
        idx = bin_search(lisR, A[i], j)
        lisR[idx] = A[i]
        ansR[i] = idx + 1

maxV = 0
for i in range(N):
    if maxV < ans[i] + ansR[i]:
        maxV = ans[i] + ansR[i]
print(maxV - 1)

알고리즘 유형

binary search

배운 점

LIS를 풀 때는 당연히 binary search를 사용해야 하는데 처음에 DP로 풀어서 시간 초과 문제가 있었다.