문제:
반도체를 설계할 때 n개의 포트를 다른 n개의 포트와 연결해야 할 때가 있다.
예를 들어 왼쪽 그림이 n개의 포트와 다른 n개의 포트를 어떻게 연결해야 하는지를 나타낸다. 하지만 이와 같이 연결을 할 경우에는 연결선이 서로 꼬이기 때문에 이와 같이 연결할 수 없다. n개의 포트가 다른 n개의 포트와 어떻게 연결되어야 하는지가 주어졌을 때, 연결선이 서로 꼬이지(겹치지, 교차하지) 않도록 하면서 최대 몇 개까지 연결할 수 있는지를 알아내는 프로그램을 작성하시오.
입력:
첫째 줄에 정수 n(1<=n<=40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, ... , n번 포트와 연결되어야 하는 포트 번호가 주어진다. 이 수들은 1 이상 n 이하이며 서로 같은 수는 없다고 가정하자.
출력:
첫째 줄에 최대 연결 개수를 출력한다.
풀이방법:
복잡해 보이지만 LIS 문제라고 생각하면 쉽게 풀 수 있다. LIS를 푸는 방법에는 여러 가지가 있지만 가장 대표적인 방법인 DP를 사용해서 문제를 풀어보았다.
|
1
2
3
4
5
6
7
8
9
10
11
|
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)
|
cs |
DP로 푸는 방법은 O(N^2)의 시간 복잡도이기 때문에 시간이 오래 걸리게 된다. 따라서 O(NlogN)으로 푸는 방법이 있다해서 다음을 참고 하였다.
https://dyngina.tistory.com/16
LIS (Longest Increasing Subsequence)
오랫만에 포스팅을 해보네요. 시험기간 (정확히 말하면 시험보는 기간입니다.) 이 되니까 별게 다 하고 싶어지네요. 이번에는 DP중에서 특별히 LIS에 대한 내용을 다뤄보려고 합니다. LIS. Longest Increasing Sub..
dyngina.tistory.com
여기서 O(NlogN)이 두 개 있었는데 lower_bound는 python의 bisect를 쓰면 될 것 같다. 이번에는 인덱스 트리를 사용해서 문제를 풀어 보았다. 인덱스 트리를 만들기 위한 과정에서 시간이 많이 소요 되는 것 같아서 이 역시도 pypy3로 통과했다. 아마도 bisect를 사용하면 python으로도 통과할 수 있을 것 같다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
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))
|
cs |
문제링크:
https://www.acmicpc.net/problem/2352
2352번: 반도체 설계
첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주어진다. 이 수들은 1 이상 n 이하이며 서로 같은 수는 없다고 가정하자.
www.acmicpc.net
'Algorithm > Python' 카테고리의 다른 글
| [BOJ]1051. 숫자 정사각형 (0) | 2020.03.26 |
|---|---|
| [BOJ]2644. 촌수계산 (0) | 2020.03.24 |
| [BOJ]1748. 수 이어 쓰기 1 (0) | 2020.03.17 |
| [BOJ]1267. 핸드폰 요금 (0) | 2020.03.12 |
| [BOJ]2579. 계단 오르기 (0) | 2020.03.10 |