★DP Upper-Advanced I - 8 Solved★

★ 12015 가장 긴 증가하는 부분 수열 2 ★

 

import sys
input=sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))

#binary search
def binary_search(l, x):
    start,end=0,len(l)-1
    while start<=end:
        mid=(start+end)//2
        if x <= l[mid]:
            end=mid-1
            ans=mid
        else:
            start=mid+1
    l[ans]=x
    return l

#LIS
ans=[A[0]]

for x in range(1,N):
    if ans[-1] < A[x]: #just add
        ans.append(A[x])
    else: #searching the spot
        ans=binary_search(ans, A[x])

print(len(ans))

 

🍜 LIS(O(nlogn)) 문제

---

★ 12738 가장 긴 증가하는 부분 수열 3 ★

 

🍜 수열 원소가 음수여도 LIS(O(nlogn)) 알고리즘은 성립

---

★ 1365 꼬인 전깃줄 ★

 

import sys
input=sys.stdin.readline

N=int(input())
n=list(map(int,input().split()))

def binary_search(l,x):
    start,end=0,len(l)-1
    while start<=end:
        mid=(start+end)//2
        if x <= l[mid]:
            ans = mid
            end = mid - 1
        else:
            start = mid + 1
    l[ans] = x
    return l

#lis(o(nlogn))
ans=[n[0]]

for x in range(1,N):
    if ans[-1] < n[x]:
        ans.append(n[x])
    else:
        ans=binary_search(ans,n[x])

print(N-len(ans))

 

🍜 꼬이지 않게 lis(O(nlogn)) 알고리즘 적용

---

★ 2352 반도체 설계 ★

import sys
input=sys.stdin.readline
n=int(input())
l = list(map(int,input().split()))

def binary_search_lis(arr,n):
    start,end=0,len(arr)-1
    while start<=end:
        mid=(start+end)//2
        if n <= arr[mid]:
            ans = mid
            end = mid-1
        else:
            start = mid+1
    arr[ans] = n
    return arr
arr=[l[0]]
for x in range(1,n):
    if arr[-1]<l[x]:
        arr.append(l[x])
    else:
        arr = binary_search_lis(arr,l[x])
print(len(arr))

 

🍜 위 1365 꼬인 전깃줄과 동일한 문제. 이분탐색을 활용한 O(nlogn) LIS 알고리즘으로 연결 가능 포트 최대 개수 구하기

---

★ 3066 브리징 시그널 ★

import sys
input=sys.stdin.readline

def binary_search_lis(arr,n):
    start,end=0,len(arr)-1
    while start<=end:
        mid=(start+end)//2
        if n <= arr[mid]:
            ans = mid
            end = mid-1
        else:
            start = mid+1
    arr[ans] = n
    return arr

for _ in range(int(input())):
    N=int(input())
    l = [int(input()) for _ in range(N)]
    arr=[l[0]]
    for x in range(1,N):
        if arr[-1]<l[x]:
            arr.append(l[x])
        else:
            arr = binary_search_lis(arr,l[x])
    print(len(arr))

 

🍜 역시 LIS(O(nlogn))으로 위 문제와 동일

---

★ 1818 책정리 ★

import sys
input=sys.stdin.readline

def binary_search_lis(arr,n):
    start,end=0,len(arr)-1
    while start<=end:
        mid=(start+end)//2
        if n < arr[mid]:
            ans = mid
            end = mid-1
        else:
            start = mid+1
    arr[ans] = n
    return arr

N=int(input())
l=list(map(int,input().split()))
arr=[l[0]]
for x in range(1,N):
    if arr[-1]<l[x]:
        arr.append(l[x])
    else:
        arr = binary_search_lis(arr,l[x])
print(N-len(arr))

 

🍜 1부터 N까지 책을 가지런하게 정리하기 위해서는, 가지런하게 정리한, 즉 책 번호가 증가하는 가장 긴 부분 수열 LIS의 길이를 구하고(이 때 책이 띄엄띄엄 있어도 상관 없다), 전체 책의 수에서 LIS의 길이를 뺀 개수만큼 본래 자리에 넣어주면 된다. LIS라는 아이디어를 사용해야 함을 기억해야 하는 유형. LIS 응용버전

---

★ 3745 오름세 ★

import sys
input=sys.stdin.readline

def binary_search_lis(arr,n):
    start,end=0,len(arr)-1
    while start<=end:
        mid=(start+end)//2
        if n <= arr[mid]:
            ans = mid
            end = mid-1
        else:
            start = mid+1
    arr[ans] = n
    return arr


while 1:
    try:
        N=int(input())
        l=list(map(int,input().split()))
        arr=[l[0]]
        for x in range(1,N):
            if arr[-1]<l[x]:
                arr.append(l[x])
            else:
                arr = binary_search_lis(arr,l[x])
        print(len(arr))
    except:
        break

 

🍜 LIS(Onlogn) 문제

---

★ 12014 주식 ★

import sys
input=sys.stdin.readline

def binary_search_lis(ar,n):
    start,end=0,len(ar)-1
    while start<=end:
        mid=(start+end)//2
        if n <= ar[mid]:
            ans = mid
            end = mid-1
        else:
            start = mid+1
    ar[ans] = n
    return ar

T=int(input())
for i in range(T):
    N,K=map(int,input().split())
    l=list(map(int,input().split()))
    arr=[l[0]]
    for x in range(1,N):
        if arr[-1]<l[x]:
            arr.append(l[x])
        else:
            arr = binary_search_lis(arr,l[x])
    if len(arr)>=K:
        print(f'Case #{i+1}')
        print(1)
    else:
        print(f'Case #{i+1}')
        print(0)

 

🍜 LIS(Onlogn) 문제

---