1365

알고리즘/acmicpc 2015. 7. 7. 18:01 Posted by 아는 개발자

전선이 꼬이지 않으려면 몇개의 전깃줄을 제거하면 되느냐는 문제는 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;
}
728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

2515  (0) 2015.07.17
2458  (0) 2015.07.15
1365  (0) 2015.07.07
7578  (0) 2015.07.06
1753  (0) 2015.07.01
1795  (0) 2015.07.01