BOJ 2352(반도체 설계)풀이

solved.ac 티어 : 골드 3

www.acmicpc.net/problem/2352

2352번: 반도체 설계

 

이문제는 연결선이 서로 꼬이지(겹치지, 교차하지) 않도록 하면서 나올 수 있는 최대 개수를 구하는 것이다. 이때 이문제에서 꼬이지 않게 하려면 i번째의 값보다 i+1번째 값이 더 커야 된다. 즉 이문제는 LIS(최장 증가 부분 수열)이라는 거다.

그러므로 이분탐색 LIS를 구해주면 된다.

import sys
sys.setrecursionlimit(1000001)
a=int(input())
l=list(map(int,input().split()))
t=[0]
def lower_bound(n):
    start=0
    end=len(t)-1
    while start < end:
        m=(start+end)//2
        if t[m]<n:
            start=m+1
        else:
            end=m
    return end
for x in range(a):
    if t[len(t)-1] < l[x]:
        t.append(l[x])
    else:
        t[lower_bound(l[x])]=l[x]
print(len(t)-1)