096 가장 긴 증가하는 부분 수열 5

첫번째 코드

 

먼저 점화식을 세우는 방법알기!!

아이디어 만들어보기!!

DP 코드 작성하는 방법 연습하기!!

 

책의 코드를 참고했다!!

 

import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
a.insert(0, 0)

index = 0
maxlength = 1
B = [0] * 1000001
D = [0] * 1000001
ans = [0] * 1000001

B[maxlength] = a[1]
D[1] = 1

def binarysearch(l, r, now):
    while l < r:
        mid = (l + r) // 2
        if B[mid] < now:
            l = mid + 1
        else:
            r = mid
    return l

for i in range(2, n+1):
    if B[maxlength] < a[i]:
        maxlength += 1
        B[maxlength] = a[i]
        D[i] = maxlength
    else:
        index = binarysearch(1, maxlength, a[i])
        B[index] = a[i]
        D[i] = index

print(maxlength)
index = maxlength
x = B[maxlength] + 1

for i in range(n, 0, -1):
    if D[i] == index:
        ans[index] = a[i]
        index -= 1

for i in range(1, maxlength+1):
    print(ans[i], end=' ')

 

통과!!

dp문제 쉬운것부터 많이 풀어보기!!

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Platinum/14003.%E2%80%85%EA%B0%80%EC%9E%A5%E2%80%85%EA%B8%B4%E2%80%85%EC%A6%9D%EA%B0%80%ED%95%98%EB%8A%94%E2%80%85%EB%B6%80%EB%B6%84%E2%80%85%EC%88%98%EC%97%B4%E2%80%855

programmers/백준/Platinum/14003. 가장 긴 증가하는 부분 수열 5 at main · ornni/programmers