백준 2352 반도체 설계
문제 설명
- 반도체 설계 시 n개의 포트를 다른 n개의 포트와 연결해야 한다.
- 왼쪽 그림과 같이 연결을 할 경우에는 연결선이 서로 꼬이기 때문에 연결할 수 없다.
오른쪽 그림과 같이 연결을 할 경우에는 서로 꼬이지(겹치지, 교차하지) 않도록 하면서 연결할 수 있다.
- 연결선이 꼬이지 않도록 하면서 최대 몇 개까지 연결할 수 있는지 출력하라.
입력 값
- 첫째 줄에 정수 n( 1<= n <= 40,000 )이 주어진다.
- 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호,
... n번 포트와 연결되어야 하는 포트 번호가 주어진다.
이 수들은 1이상 n이하이며 서로 같을 수는 없다
예제
문제 분석
- 이 문제를 자세히 살펴보면 서로 꼬이지 않고 연결하는 방법은
a번 포트가 b번 포트에 연결되었을 때 a보다 큰 포트는 b보다 큰 포트에 연결되어야 한다.
- 즉, 1번 포트가 3번 포트에 연결된 경우, 2~n번 포트는 무조건 3번 보다 큰 포트에 연결되어야 한다는 것이다.
- 이것을 정리하면, i번째 포트가 연결되는 포트를 j라고 가정하면, X[i] = j 라고 하자.
X[i+1] >= j+1이어야한 연결이 가능하다는 것이다.
- 결국 이것이 의미하는 것은 배열 X가 주어졌을 때 점점 증가하는 가장 긴 부분 수열을 찾는 것이다.
- 즉, LIS 문제이다.
- N의 최대 크기가 40,000이기 때문에 NlogN의 시간복잡도를 가진 DP + 이분탐색의 LIS를 사용해야 한다.
소스 코드
#include <bits/stdc++.h>
using namespace std;
int arr[400001];
int dp[400001];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N;
cin >> N;
int maxLast = 1;
for (int i = 0; i < N; i++) {
int n;
cin >> n;
arr[i + 1] = n;
}
dp[1] = arr[1];
for (int i = 1; i <= N; i++) {
int start = 1;
int last = maxLast;
while (start <= last) {
int mid = (start + last) / 2;
if (arr[i] == dp[mid]) {
start = mid;
break;
}
else if (arr[i] < dp[mid]) {
last = mid - 1;
}
else {
start = mid + 1;
}
}
dp[start] = arr[i];
maxLast = max(maxLast, start);
}
cout << maxLast << endl;
return 0;
}
'알고리즘 > 알고리즘 문제풀이' 카테고리의 다른 글
[BOJ-2461] 대표 선수(C++) (0) | 2021.07.17 |
---|---|
[BOJ-21925 ] 짝수 팰린드롬(C++) (0) | 2021.07.16 |
[BOJ-1916] 최소비용 구하기(C++) (0) | 2021.07.14 |
[BOJ-2325] 개코전쟁(C++) (0) | 2021.07.13 |
[BOJ-2283] 구간 자르기(C++) (0) | 2021.07.10 |
댓글