1. 문제

---

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

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

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

2. 아이디어

---

• mine + clone (❗)

  1. LIS(가장 긴 증가하는 부분 수열)를 사용해야 되는 것은 알았지만 파이썬 bisect로 구현할 줄 몰라서 찾아봄.
  2. 이해를 위해 파이썬 튜터 사용 (http://pythontutor.com/visualize.html#mode=display)
  3. bisect로 L에 들어갈 위치를 찾아서 넣거나 추가해주는 방법(코드와 파이썬 튜터 참고)

출처 : https://lgphone.tistory.com/129

3. 코드

---

mine + clone

import sys
input = sys.stdin.readline

# O(N log N)
from bisect import bisect_left

def get_lis_improved(sequence):
  L = [sequence[0]]
  for i in range(1, len(sequence)):
    if L[-1] < sequence[i]:
      L.append(sequence[i])
    else:
      lower_bound = bisect_left(L, sequence[i])
      L[lower_bound] = sequence[i]
  # print(L)
  return len(L)

n = int(input())
arr = list(map(int, input().split()))
print(get_lis_improved(arr))