글 읽기 - 시간초과가 왜 나는걸까요? 궁금합니다.

kth004 7년 전 0

아래는 제가 작성한 코드인데요. bfs로 하였으며 중복값도 제거를 했는데 시간초과가 나네요. 왜 그런지 이유를 모르겠습니다.

알려주시면 감사드리겠습니다.

#include<iostream>
#include<set>
#include<cstdio>
#include<queue>
using namespace std;

queue<pair<int,int>> q;
set<int> se;
int dist[2];
int g,f,s,u,d;
int main(){
	int i,ans;
	ans=0;
	scanf("%d%d%d%d%d",&f,&s,&g,&u,&d);
	/* 현재 층수가 도착 층수보다 높은데 아래로 못내려갈경우
	   현재 층수가 도착 층수보다 낮은데 위로 못올라갈겨우,*/
	if((s<g && u==0) ||(s>g && d==0)){  // 
		printf("use the stairs\n"); 
		return 0;
	}
	else if(s==g){ // 현재 층수와 도착 층수가 같을 경우. 
		printf("%d\n",ans);
		return 0;
	}
	dist[0]=u; // 위로 올라가는 층.
	dist[1]=d; // 아래로 내려가는 층. 
	q.push(make_pair(s,0));
	se.insert(s);
	int x,cnt,px;
	bool IsTrue=false;
	while(!q.empty()){
		pair<int,int> p;
		p=q.front();
		x=p.first; // 현재 층수. 
		cnt=p.second; // 움직인 횟수. 

		for(i=0;i<2;i++){
			if(i==0 && x+dist[i]<=f) px=x+dist[i]; 
			if(i==1 && x-dist[i]>=1) px=x-dist[i];

			if(se.find(px)==se.end()){ // 방문을 안했을경우. 
				if(px==g){ // 도착했을 때. 
				IsTrue=true;
				ans=cnt+1;
				break;
				}
				q.push(make_pair(px,cnt+1));
				se.insert(px);
			}
		}
		q.pop();
		if(IsTrue) break;
	}

	printf("%d\n",ans);
	return 0;
}

midinpa 6년 전 2

큐에 처음 넣는 시작점을 주어지는 s 말고 g에 가까운 값으로 해서 넣으세요~
ex) g = 100, s = 1, u =2, d = 1

이럴 경우 (g - s) / u = 49 인 것을 이용해서
시작점을 s + 49*u (99)로 잡고 distance를 49로 세팅해두고 bfs를 시작하면 더 금방될꺼에요~

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

문제

문제

출처

ICPC

시간초과가 왜 나는걸까요? 궁금합니다.

kth004 7년 전 0

midinpa 6년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말