[백준 2565] 전깃줄

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

문제 요약

전깃줄이 어린이 학습지 짝짓기 문제처럼 복잡하게 얽혀있다.
남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 출력한다.

입력

첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다.

출력

첫째 줄에 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 출력한다.

아이디어

왼쪽에서 나와 오른쪽이 목적지라 할 때 왼쪽이 갖는 목적지를 왼쪽 옆에 적었을 때(목적지의순열생성됨) 오름차순 연결되면 교차하지 않는다
근데 이런 오름차순 부분순열 중에 가장 큰 것 ->LIS 응용문제

내 옛날 코드를 보면... 마지막에 지워야할 전선의 최솟값을 구할 때 각 증가하는 부분수열들을 하나씩 거쳐보며... 최댓값을 구하는데 이렇게 이중 for문을 왜 돌았는지 지금은 이해가 안된다.
그냥 b[i]를 꼬리로 하는 가장긴 증가하는 부분순열 길이인 lis[i] 값이 저장된 배열을 쭉 훓으면서 최댓값 찾은 후에 전선수 - lis 최댓값 하면 될 것같긴하다.

코드

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
//lis
int main() {
	int n;
	cin >> n;
	//map<int, int> a;
	int a[500];
	int b[500];//그대로 자신을 마지막으로 하는 lis
	int c[500];//tracking 
	int idx=0,value= 0;

	for (int i = 0; i < 500; i++) {
		a[i] = -1;
		b[i] = -1;
		c[i] = -1;
	}

	for (int i = 0; i < n; i++) {
		cin >> idx>>value;

		a[idx - 1] = value;
	}
	b[0] = 1;
	c[0] = -1;//-1 means end of tracking

	for (int i = 0; i < 500; i++) {
		if (a[i] == -1) {
			continue;
		}

		b[i] = 1;
		c[i] = -1;
		for (int j = 0; j < i; j++) {
			if (a[j] == -1) {
				continue;
			}

			if (a[j] < a[i]) {

				if (b[i] < b[j] + 1) {//b를 살려두는 이유는 작은 벡터 사이즈 접근하기 싫어서
					b[i] = b[j] + 1;
					c[i] = j;//계열 후보
				}
				
			}
			
		}
	}
	int res = 0;
	
	for (int i = 500 - 1; i >= 0; i--) {
		if (a[i] == -1) {
			continue;
		}
		int candidate = 0;
		for (int j = i; j != -1; j = c[j]) {
			candidate++;
		}
		res = max(res, candidate);
	}

	cout << n - res << endl;

}