1365

전선이 꼬이지 않으려면 몇개의 전깃줄을 제거하면 되느냐는 문제는 LIS의 변형 문제와 같다.

연결되어있는 전선들 각각에 수치들을 준다면 하나도 꼬이지 않은 형태는 연결된 전선들이 증가하는 순열의 모양새와 같을 것이다.

이 순열들 중에서 가장 긴 순열을 찾으면 잘라내야하는 전선의 수도 자동적으로 알수있다.

(잘라내야하는 전선의 수 = 총 전선의 수 - 가장 긴 순열에 포함된 전선의 수)

LIS 는 기본적으로 dp를 이용해서 해결하는데 어떻게 푸느냐에 따라서 시간 복잡도가 다르다

예전에 for문을 두번 돌린 O(n^2)로 풀다가 조금 더 개선된 방법인 우선순위 큐를 사용했었지만 여기서는 우선순위큐로도 시간초과가 떴다

꽤 고민했지만 찾을수 없어 LIS 알고리즘을 인터넷으로 참고해보니 인덱스 트리를 사용하는 방법이 있었다. 

각각의 전선들은 자신과 연결된 전선들 보다 작은 값을 가지는 것 중에서 현재 가장 길게 연결된 순열을 찾아야 한다. 내가 연결되는 전선이 i라고 하면 0~i-1 구간 중에서 최장 증가 순열을 찾아야 한다는 것이다. 이때 이것을 단순히 탐색 알고리즘을 하면 O(N)의 시간이 걸리지만, 인덱스트리를 통해 각 구간별로 최대값을 찾도록 하면 O(logN) 시간 내에 찾을 수 있다.

인덱스 트리 만드는것은 만만치 않고 중간에 실수하면 디버깅하는데 시간이 오래 걸린다. 나는 각각의 노드에서 구간을 정리하는데 시간이 오래걸렸다...

 
#include<iostream>
#include<cstdio>

using namespace std;

int tree[20][100000];



void update(int height, int piv, int data){
	if(height==18)
		return;

	if(tree[height][piv] < data){
		tree[height][piv] = data;
		update(height+1, piv/2, data);
		return;
	}
}

int myPow(int height){
	int ret=1;
	for(int i=0; i<height; i++){
		ret*=2;
	}
	return ret;
}

int findMax(int height, int piv, int from, int to){
	
	int range=myPow(height)-1;

	if(from > to)
		return 0;

	int hereFrom = myPow(height)*piv;
	int hereTo = myPow(height)*piv+range;
	if(hereFrom==from && hereTo==to)
		return tree[height][piv];

	if(hereFrom>to || hereFrom+range < from)
		return 0;

	return max(findMax(height-1, piv*2, from, min(to, hereFrom+myPow(height-1)-1)),
		findMax(height-1, piv*2+1, max(from, hereFrom+myPow(height-1)), to));
}

int main()
{
	int n, idx, cur, ret;
	scanf("%d", &n);

	ret = 0;

	for(int i=0; i<n; i++){
		scanf("%d", &idx);
		cur = findMax(17, 0, 0, idx-1) + 1;
		ret = max(ret, cur);
		update(0, idx-1, cur);
	}

	printf("%d\n", n-ret);

	return 0;
}