글 읽기 - 숨바꼭질4 메모리초과 문제

gdkim4137 7년 전 0

코딩 후 테스트해봤는데, 메모리 초과때문에 pass를 못하고 있네요.

관련 글을 찾아보다가 우연히 http://www.crocus.co.kr/637 블로그를 발견하였고

이 코드를 돌리니까 되던데, 제 코드랑 무슨 차이가 있죠??

조언좀 부탁드리겠습니다.

#include<iostream>
#include<fstream>
#include<queue>
#include<stack>

using namespace std;
#define N_MAX	100000
int trace[N_MAX+1] = { 0 };
int main()
{
	int from, to;
	cin >> from >> to;

	//	first  : number
	//	second : cost
	queue<pair<int, int>> Q;

	int optimal_cost = 9999999;
	int counter = 0;

	Q.push(pair<int, int>(from, 0));
	while (!Q.empty())
	{
		pair<int, int> now = Q.front();
		int number = now.first;
		int cost = now.second;
		Q.pop();

		if (number == to)
		{
			optimal_cost = min(cost, optimal_cost);
			counter++;
			break;
		}
		if (0 <= number - 1 && number - 1 <= N_MAX && trace[number - 1] == 0)
		{
			trace[number - 1] = number;
			Q.push(pair<int, int>(number - 1, cost + 1));
		}
		if (0 <= number + 1 && number + 1 <= N_MAX && trace[number + 1] == 0)
		{
			trace[number + 1] = number;
			Q.push(pair<int, int>(number + 1, cost + 1));
		}
		if (0 <= number * 2 && number * 2 <= N_MAX && trace[number * 2] == 0)
		{
			trace[number * 2] = number;
			Q.push(pair<int, int>(number * 2, cost + 1));
		}
	}
	std::cout << optimal_cost << std::endl;
	
	int vertex = to;
	stack<int> path;
	
	path.push(vertex);
	do
	{
		vertex = trace[vertex];
		path.push(vertex);
	} while (vertex != from);

	while (!path.empty())
	{
		int number = path.top();
		cout << number << " ";
		path.pop();
	}

	return 0;
}

nisroeld99 7년 전 1

확인은 안해봤습니다만은 n==k 일경우..?

gdkim4137 7년 전 0

nisroeld99 우선 찾아주신 점 감사드립니다. 하지만 n==k 경우를 처리하여도 같은 문제가 발생하네요...

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

문제

문제

출처

ICPC

숨바꼭질4 메모리초과 문제

gdkim4137 7년 전 0

nisroeld99 7년 전 1

gdkim4137 7년 전 0

nisroeld99 우선 찾아주신 점 감사드립니다. 하지만 n==k 경우를 처리하여도 같은 문제가 발생하네요...

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말