[백준/파이썬] 12015번 가장 긴 증가하는 부분 수열 2

-Code

def binary(arr, target, s, e):
    while s < e:
        mid = (s + e) // 2
        if target <= arr[mid]:
            e = mid
        elif target > arr[mid]:
            s = mid + 1
    return e


n = int(input())
nums = list(map(int, input().split()))
dp = [0]
for num in nums:
    if dp[-1] < num:
        dp.append(num)
    else:
        p = binary(dp, num, 0, len(dp) - 1)
        dp[p] = num
print(len(dp) - 1)

LIS에 대해서 풀다가 이해를 못 하는 것 같아서 원리를 아예 찾아보고 이분 탐색의 경우 이해하는 것에 많이 걸렸습니다.

이진 탐색 코드는 짜는데 return을 어떻게 해줘야하는 지와 dp자체의 숫자에 의미가 없고  LIS의 길이만 구할 때 사용하는 것이라는 것을 알게 되어 해결했지만 아쉬웠습니다.