가즈아아아 꾸준히

문제

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

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

입력

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

출력

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

<출처> https://www.acmicpc.net/

이 문제를 풀다풀다 계속 오답이 나오길래 구글링을 통해 다른 분들의 해법을 보았다.

그런데 도무지 이해가 되지 않는 점이 ... 1가지 있었다..

먼저 LIS의 개념을 모르시는 분들을 위해

참고 사이트 : http://dyngina.tistory.com/16

다른 분들의 풀이를 보면 LIS를 이용해 풀었다. 나 또한 LIS의 개념은 일부 맞지만 이 문제의 핵심인 "선이 교차하지 않는것" 이 부분을 어긴다? 라고 생각이 들었는데 정답 처리가 되어 더 혼란속으로 빠져들었다...

이런식으로 주어졌을 때 (2와2),(4와3),(6과5) 이렇게 이어졌을 때 겹치지 않으면서 최대로 연결할 수 있다.

다른 분들의 풀이를 보면 LIS를 토대로 (2와2)(4와3)까지 이어졌을 때 오른쪽에 있는 1이 들어갈 최적의 위치를 계산해서 (2와2)를 제거하고 대신 들어가게 된다.

그러면 겹치는 선이 아닌가?? 여기서 의문이 들었다.... 지금도 모르겠다...

나는 선이 겹치는 문제 때문에 아래와 같은 방식으로 했었다.

check[1] = weight[1];
	int idx = 1;
	for (int i = 2; i <= N; i++) {
		if (check[idx] < weight[i]) {
			check[++idx] = weight[i];
			continue;
		}
		if (idx == 1) {
			check[idx] = weight[i];
		}
		else if (check[idx - 1] < weight[i]) {
			for(int k=)
			check[idx] = weight[i];
		}
	}

<마지막에 들어간 수보다 작고, 마지막 보다 한칸 전에 들어간 수보다 크다면 마지막을 대신해 넣고 작다면 아무것도 하지 않는다. 작다면 겹치는 문제가 발생하기 때문!> 이라고 생각했다. 

지금도 왜 안되는지 모르겠다.. 혹시 아시는분이 계시면 댓글로 알려주시면 감사하겠습니다!!!

결론적으로, 이 부분만 참고했고 고쳐서 통과했다.

#include<iostream>
#include<algorithm>

using namespace std;
int N;
int weight[40001];
int check[40001];
int main() {

	cin >> N;

	for (int i = 1; i <=N; i++) {
		cin >> weight[i];
	}
	check[1] = weight[1];
	int idx = 1;
	for (int i = 2; i <= N; i++) {
		if (check[idx] < weight[i]) {
			check[++idx] = weight[i];
			continue;
		}
		int iter = lower_bound(check + 1, check + 1 + idx, weight[i]) - check;
		check[iter] = weight[i];
	}
	cout << idx << endl;
}