문제
반도체를 설계할 때 n개의 포트를 다른 n개의 포트와 연결해야 할 때가 있다.
예를 들어 왼쪽 그림이 n개의 포트와 다른 n개의 포트를 어떻게 연결해야 하는지를 나타낸다. 하지만 이와 같이 연결을 할 경우에는 연결선이 서로 꼬이기 때문에 이와 같이 연결할 수 없다. n개의 포트가 다른 n개의 포트와 어떻게 연결되어야 하는지가 주어졌을 때, 연결선이 서로 꼬이지(겹치지, 교차하지) 않도록 하면서 최대 몇 개까지 연결할 수 있는지를 알아내는 프로그램을 작성하시오
입력
첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주어진다. 이 수들은 1 이상 n 이하이며 서로 같은 수는 없다고 가정하자.
출력
첫째 줄에 최대 연결 개수를 출력한다.
풀이
n개의 포트를 다른 n개의 포트와 연결해야 한다.
이때, n개의 포트마다 각각 배정된 포트가 있는데 이를 최대한 많이 꼬이지 않게 하는 문제이다.
꼬이지 않고 최대한 많이 하려면 포트가 증가하되, 되도록 적게 증가하면서 많이 연결해야 한다(?)
최장 부분 증가 수열로 만들면 된다는 것이다.
초반에 문제의 이해를 잘못해서 최장 부분 증가 수열을 하나 만들고, 입력을 뒤집어 뒤집은 최장 부분 증가 수열의 길이를 만드는 것인 줄 알았다.
문제를 잘 살펴보면 그렇지 않다. (나는 그걸 테스트케이스로 알았다.)
입력을 잘 살펴보면 1번 포트부터 차례대로 연결해야 하는 포트 번호가 오고 있다. 이를 역순으로 뒤집게 되면 포트 번호 또한 뒤집어야 되는데, 인덱스를 뒤집지 않게 되면 각 포트별로 연결하는 포트가 달라지게 된다.
또한 인덱스도 뒤집는다면 기존과 다를게 없어지게 되므로, 그냥 동일한 배열이된다.
결론 : 평범한 최장 부분 증가 수열 문제였다.
기존의 nlogn 최장 부분 증가 수열 풀이를 이용하여 해결했다.
from bisect import bisect_left
def lis(arr, N):
# n log n LIS algorithm
k = []
l_k = []
for i in range(N):
idx = bisect_left(k, arr[i])
if idx == len(k): k.append(arr[i])
else: k[idx] = arr[i]
l_k.append(idx+1)
return l_k
input = open(0).readline
N = int(input())
port = [*map(int, input().split())]
ans = max(lis(port, N))
print(ans)
