글 읽기 - 시간초과 질문드립니다.

p_ce1052 4년 전 1

이진탐색으로 풀었습니다. 한 변의 크기가 x인 정사각형으로 커버가 되면 그 위의 크기로는 전부 커버가 되니 크기를 줄이고 x로 커버가 안되면 x미만의 값들로도 커버가 안되니 크기를 올리는 식으로 해서 값을 찾았습니다. 특정 크기 x에 대해 최소 장수로 덮는 알고리즘은 점의 좌표를 입력받아서 정렬하고 solve에서 가로축으로 봤을 때 한 번에 x크기만큼 구간을 잘라서 각 구간 안의 y좌표들을 res에 저장하고 solve2에서 y좌표들만 고려하여 수직선 상에서 x길이의 선분 최소개수로 주어진 점들을 모두 덮는 문제로 바꿔서 풀고 더해주었습니다. 아무리 오래걸려도 o((점 개수^2)log(max(행 ,렬))을 안넘는다고 생각했는데 시간초과가 납니다. 여기서 어떻게 더 시간을 줄일 수 있나요?

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int x,y;
int paper;
vector<pair<int,int> >coords;
vector<int>res;
int solve2(int psize){
	int i=0;
	int counter=0;
	while(i<res.size()){
		int start=i;
		int ender=i;
		while(ender<res.size() && res[ender]-res[start]+1<=psize) ender++;
		ender--;
		counter++;
		i=ender+1;
	}
	return counter;
}
bool solve(int psize){
	int i=0;
	int sum=0;
	while(i<coords.size()){
		int start = i;
		int ender = i;
		while(ender<coords.size() && coords[ender].first-coords[start].first+1<=psize){
			ender++; //psize보다 큰 구간이 될 때까지 이동
		}
		ender--; //구간이 더 커졌거나 배열 밖으로 나갔으니 감소 
		res.clear();
		for(int j=start; j<=ender; j++) res.push_back(coords[j].second); //y좌표만을 옮겨담는다.
		sort(res.begin(),res.end()); //정렬
		sum+=solve2(psize); //수직선 상의 문제로 넘겨서 푼다. 
		i=ender+1;
	}
	if(sum<=paper) return true;
	else return false;
} 
int main(){
	cin>>y>>x>>paper;
	int n;
	cin>>n;
	coords = vector<pair<int,int> >(n);
	for(int i=0; i<n; i++){
		cin>>coords[i].second>>coords[i].first;
	}
	sort(coords.begin(),coords.end());
	int start = 1;
	int end = min(x,y);
	while(start<end){
		int mid = (start+end)/2;
		if(solve(mid)) end=mid; //가능하면 더 큰 애들에 대해서는 당연히 되니 크기를 줄인다. 
		else start=mid;  //불가능하면 더 작은 애들에 대해서는 당연히 안되니 크기를 늘인다.  
	}
	if(solve(start)) cout<<start; //둘이 1차이나는 상황에서 안풀려서 1을 올렸을테니 풀리면 이게 정답 
	else cout<<start+1; //start+1로 되니까 밑으로 내려왔을테니 start가 안되면 다시 올라간다.  
}

p_ce1052 4년 전 0

해결됬습니다 무한루프는 mid값을 계속 왔다갔다해서 발생하는 거였네요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과 질문드립니다.

p_ce1052 4년 전 1

p_ce1052 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말