[BOJ]2352. 반도체 설계

문제:

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

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

입력:

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

출력:

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

풀이방법:

복잡해 보이지만 LIS 문제라고 생각하면 쉽게 풀 수 있다. LIS를 푸는 방법에는 여러 가지가 있지만 가장 대표적인 방법인 DP를 사용해서 문제를 풀어보았다.

n=int(input())
ports=list(map(int,input().split()))
 
dp=[0]*n
 
for i in range(1,n):
    for j in range(i):
        if ports[i] > ports[j] and dp[i] < dp[j]+1:
            dp[i]=dp[j]+1
            
print(dp[-1]+1)

DP로 푸는 방법은 O(N^2)의 시간 복잡도이기 때문에 시간이 오래 걸리게 된다. 따라서 O(NlogN)으로 푸는 방법이 있다해서 다음을 참고 하였다.

https://dyngina.tistory.com/16

LIS (Longest Increasing Subsequence)

여기서 O(NlogN)이 두 개 있었는데 lower_bound는 python의 bisect를 쓰면 될 것 같다. 이번에는 인덱스 트리를 사용해서 문제를 풀어 보았다. 인덱스 트리를 만들기 위한 과정에서 시간이 많이 소요 되는 것 같아서 이 역시도 pypy3로 통과했다. 아마도 bisect를 사용하면 python으로도 통과할 수 있을 것 같다.

n=int(input())
ports=list(map(int,input().split()))
 
for i in range(n):
    ports[i]=(ports[i],i+1)
ports.sort()
 
dp=[0]*n
for i in range(n):
    idx=ports[i][1]
    maxTemp=0
    for j in range(idx):
        if dp[j] > maxTemp:
            maxTemp=dp[j]
    dp[idx-1]=maxTemp+1
print(max(dp))

문제링크:

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

2352번: 반도체 설계