[BaekJoon] 백준 2352번 반도체 설계

[BaekJoon] 백준 2352번 반도체 설계

 

🎈문제

https://www.acmicpc.net/problem/2352

💬설명

LIS 문제인데 DP로 풀게되면 시간초과가 난다.

이분탐색으로 문제를 풀어줘야 한다.

👩‍💻코드

# BaekJoon 2352.py

N = int(input())
arr = list(map(int, input().split()))
lst = []


# 이분 탐색으로 lower bound 찾아주기
def find(s, e, v):
    global lst
    while s < e:
        m = (s + e) // 2
        if lst[m] < v:
            s = m + 1
        else:
            e = m
    return e


for i in range(N):
    # 첫번째 숫자인 경우
    if i == 0:
        lst.append(arr[i])
    else:
        # 증가하는 수열이면
        if arr[i] > lst[-1]:
            lst.append(arr[i])
        # 감소하는 수열이면 이분탐색으로 자리 찾기
        else:
            # 0부터 len(lst)사이의 lst배열에서 arr[i]의 위치 찾아서 lst에 넣어주기기
            lst[find(0, len(lst), arr[i])] = arr[i]

print(len(lst))

👉참고

https://0equal2.tistory.com/101