★DP Upper-Advanced I - 9 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) 문제

---

★ 2655 가장높은탑쌓기 ★

import sys
input=sys.stdin.readline

n = int(input())

dp = [[0, []] for _ in range(n)] #[height, [brick_nums listed]]
bricks = []
for i in range(n):
    s,h,w = map(int,input().split())
    bricks.append((s,h,w,i+1))
bricks_sorted = sorted(bricks,key = lambda x : x[0])

#dp initialization
for i in range(n):
    cur_h, cur_num = bricks_sorted[i][1], bricks_sorted[i][3]
    dp[i][0] = cur_h
    dp[i][1] = [cur_num]

for i in range(1,n):
    cur_num = bricks_sorted[i][3]
    cur_w = bricks_sorted[i][2] #check only by w
    cur_h = bricks_sorted[i][1]
    for x in range(i):
        last_brick_num = dp[x][-1][-1]
        last_brick_weight = bricks[last_brick_num-1][2]
        last_brick_height = bricks[last_brick_num-1][1]
        if last_brick_weight < cur_w:
            if dp[i][0] < cur_h + dp[x][0]: #dp update
                dp[i][0] = cur_h + dp[x][0]
                dp[i][1] = dp[x][1] + [cur_num]
dp.sort(key = lambda x: x[0])
print(len(dp[-1][-1]))
print(*dp[-1][1], sep = '\n')

 

🍜 예시에 주어진 (밑면 S, 높이, 무게, 블록번호)인 블록들을 나열해보면

 

25 3 4 1

4 4 6 2

9 2 3 3

16 2 5 4

1 5 2 5

 

(1) DP 아이디어를 사용. DP의 구성성분은 2개로 각 블록이 무조건 아래의 블록으로 들어가 있다고 가정했을 때의 height와 그 때의 블록 번호 조합 list(즉, LIS의 dp와 완전히 똑같다고 보면 된다)

 

(2) 즉 DP initialization 위해 밑면 S 오름차순 기준으로 정렬.

 

1 5 2 5

4 4 6 2

9 2 3 3

16 2 5 4

25 3 4 1

 

(3) DP initialization. 일단, 각 dp 구성성분에 해당 brick(sorted된 brick 기준으로 진행)이 무조건 들어가야 하므로 현재 brick의 height / number dp로 update.

[[5, [5]], [4, [2]], [2, [3]], [2, [4]], [3, [1]]]

 

(4) LIS 알고리즘으로 sorted된 bricks 기준으로 이중 for문(O(n^2)) 돌면서 현재 index i, 즉 dp[i]를 채운다고 했을 때, for x in range(i)로 돌면서 ① 앞선 brick x에서의 weight보다 현재 index i에서의 weight가 더 크고, ② 현재 dp[i]의 height보다 (앞선 brick x에서의 dp[x]의 height(즉, brick x를 밑바닥으로 했을 때의 최고 높이) + 현재 index i에서의 height)가 더 크다면, dp의 두 요소 update

 

[[5, [5]], [9, [5, 2]], [7, [5, 3]], [9, [5, 3, 4]], [10, [5, 3, 1]]]

 

(5) dp의 구성요소 첫번째 중 최댓값에서의 두번째 요소 brick number와 두번째 요소의 길이(the number of bricks) 각각 출력하면 끝!

---