글 읽기 - 왜 시간초과가 안나나요?

p_ce1052 3년 전 0

두 엘레베이터가 연결되어 있음을 판단할 때

y1 = a*x1+b, y2 = c*x2+d 어떤 두 x1,x2에 대해 y1==y2이고, y1은 정수이고 1<=y1<=n이 되는 x1,x2가 있는지 확인해야 하는데

이걸 그냥 나이브하게 b에 a를 계속 더해가면서 확인하였습니다.

최악의 경우에 100000 * 5500 으로 1초를 훌쩍 넘어갈 것 같은데 시간초과가 안나네요

원래 정해가 무엇인지 궁금합니다. 만약 위의 방법이 정해라면 시간초과가 나지 않을거라고 어디서 근거를 잡는지 궁금합니다.

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pi;
int INF = INT32_MAX;
int n,m;
int graph[105][105];
vector<int>dp;
vector<pi>arr;
int fin[105];
int st[105];
bool judge(int i,int j){
	int a = arr[i].second;
	int b = arr[i].first;
	int c = arr[j].second;
	int d = arr[j].first;
	//ax+b = cy+d = 정수인 x,y가 존재하는가? 
	if(b==d) return true;
	while(b<=n){
		if(b>=d && (b-d)%c==0) return true;
		b+=a;
	}
	return false;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>m;
	dp = vector<int>(m+1,INF);
	arr = vector<pi>(m+1);
	for(int i=1; i<=m; i++) cin>>arr[i].first>>arr[i].second;
	int a,b;
	cin>>a>>b;
	
	for(int j=1; j<=m; j++){
		int start = arr[j].first;
		int x = arr[j].second;
		for(int i=start; i<=n; i+=x){
			if(i==a) st[j] = true;
			if(i==b) fin[j] = true;
		}
	}

	for(int i=1; i<=m; i++){
		for(int j=i+1; j<=m; j++){
			if(judge(i,j)){
				graph[i][j] = true;
				graph[j][i] = true;
			}
		}
	}
	queue<pi>q;
	for(int i=1; i<=m; i++){
		if(st[i]){
			q.push(pi(i,0));
			dp[i] = 0;
		}
	}
	while(!q.empty()){
		int cur = q.front().first;
		int d = q.front().second;
		q.pop();
		for(int i=1; i<=m; i++){
			if(graph[cur][i] && dp[i]==INF){
				dp[i] = d+1;
				q.push(pi(i,dp[i]));
			}
		}
	}
	int mindist = INT32_MAX;
	int fin_elv = -1;
	for(int i=1; i<=m; i++){
		if(fin[i]){
			if(mindist>dp[i]){
				mindist = dp[i];
				fin_elv = i;
			}
		}
	}
	if(mindist==INT32_MAX) cout<<-1;
	else{

		cout<<mindist+1<<'\n';
		vector<int>ans;
		while(1){
			ans.push_back(fin_elv);
			if(mindist==0) break;
			for(int i=1; i<=m; i++){
				if(graph[fin_elv][i] && dp[i]==mindist-1){
					mindist = dp[i];
					fin_elv = i;
					break;
				}
			}
		}
		reverse(ans.begin(),ans.end());
		for(int i=0; i<ans.size(); i++) cout<<ans[i]<<'\n';
	}
}
//위 문제를 풀기 위해 필요한 것 ax+b = cy+d를 만족하는 n이하의 정수가 존재하는가 

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

문제

문제

출처

ICPC

왜 시간초과가 안나나요?

p_ce1052 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말