글 읽기 - 시간초과 질문입니다. ㅠㅠ

sukwoo0711 7년 전 0

일단 답은 제대로 나오는 것 같아요.. 근데 시간초과가 ㅠㅠㅠㅠㅠㅠㅠ

알고리즘은 아래와 같습니다.

1.입력받은 숫자의 -1, +1, *2 값이 범위안에 속하는지 확인

2.큐에 삽입하기 전, 목표하는 값과 일치하는지 확인(만약 일치하면, 큐에 넣지않고 dp값만 갱신후 바로 break

3.같은 값이 2번 삽입되는것을 막기위해 check배열을 이용하여 이중삽입 방지

가지 칠 수 있는건 다 친거같은데 왜이럴까요???

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
//#include <Windows.h>

#define MAX 100000
int map[100001];
int dp[100001];
int visit[100001];
int n, m, front, rear;
int queue[100001];
int _min(int a, int b)
{
	if (a > b)
		return b;
	else
		return a;
}
void enque(int x)
{
	//printf("enqued = %d\n", x);
	queue[rear++%MAX] = x;
}
int deque()
{
	//printf("dequed = %d\n", queue[front]);
	return queue[front++%MAX];
}
int isEmpty()
{
	if (front == rear)
		return 1;
	else
		return 0;
}
void bfs(int start, int dest)
{
	static int check[100001];
	int t = 0;
	enque(start);
	check[start] = 1;
	dp[start] = 1;
	while (t!=dest)
	{
		t = deque();
		if (t * 2 < MAX)
		{
			if (check[t * 2] == 0) {
				dp[t * 2] = _min(dp[t * 2], dp[t] + 1);
				if (t * 2 == dest)
					break;
				else{
				enque(t * 2);
				check[t * 2] = 1;
				}
			}
		}
		if (t - 1 >= 0)
		{
			if (check[t - 1] == 0) {
				dp[t - 1] = _min(dp[t] + 1, dp[t - 1]);
				if (t - 1 == dest)
				{
					break;
				}
				else {
					enque(t - 1);
					check[t - 1] = 1;
				}
			}
		}
		
		if (t + 1 < MAX)
		{
			if (check[t + 1] == 0) {
				dp[t + 1] = _min(dp[t + 1], dp[t] + 1);
				if (t + 1 == dest)
					break;
				else {
					enque(t + 1);
					check[t + 1] = 1;
				}
			}
		}
		
	}
}
int main()
{
	memset(dp, 99, sizeof(dp));
	scanf("%d %d", &n, &m);
	if (n > m){
		bfs(m, n);
		printf("%d", dp[n] - 1);
	}
	else{
		bfs(n, m);
		printf("%d", dp[m] - 1);
	}
}

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

문제

문제

출처

ICPC

시간초과 질문입니다. ㅠㅠ

sukwoo0711 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말