[백준 2352] 반도체 설계

문제

반도체를 설계할 때 n개의 포트를 다른 n개의 포트와 연결해야 할 때가 있다.

예를 들어 왼쪽 그림이 n개의 포트와 다른 n개의 포트를 어떻게 연결해야 하는지를 나타낸다. 하지만 이와 같이 연결을 할 경우에는 연결선이 서로 꼬이기 때문에 이와 같이 연결할 수 없다. n개의 포트가 다른 n개의 포트와 어떻게 연결되어야 하는지가 주어졌을 때, 연결선이 서로 꼬이지(겹치지, 교차하지) 않도록 하면서 최대 몇 개까지 연결할 수 있는지를 알아내는 프로그램을 작성하시오

 

입력

첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주어진다. 이 수들은 1 이상 n 이하이며 서로 같은 수는 없다고 가정하자.

 

출력

첫째 줄에 최대 연결 개수를 출력한다.

---

접근

문제대로 시뮬레이션을 했을 때 연결선이 교차하지 않도록 하면서 최대로 연결하는 선의 수는 LIS라는 것을 확인할 수 있었다.

따라서 LIS를 이진탐색으로 구현하였다.

 

구현

- lis에 첫 번째 원소를 넣는다.

- 이제 lis의 마지막 원소와 현재 원소를 비교하여 현재 원소가 크다면 lis에 추가하고

- 작다면 들어갈 자리를 이진탐색으로 찾는다.

- 이진탐색으로 전달받은 인덱스에 현재 원소를 넣는다.

- 마지막으로 lis의 길이를 출력한다.

import sys
input = sys.stdin.readline

def binary_search(left, right, target):
    while left < right:
        mid = (left + right) // 2
        if lis[mid] < target:
            left = mid + 1
        else:
            right = mid

    return right

N = int(input())
numbers = list(map(int, input().split()))
lis = [numbers[0],]

for i in range(1, N):
    if lis[-1] < numbers[i]:
        lis.append(numbers[i])
    else:
        idx = binary_search(0, len(lis)-1, numbers[i])
        lis[idx] = numbers[i]

print(len(lis))