글 읽기 - 반례 부탁드립니다.

shapins 4년 전 0

테스트 샘플 몇개 입력 해봤는데

맞게는 나오나..

어떤부분에서 틀렸는지 모르겠습니다..

반례 부탁드려요 ㅜㅜ

/*
문제
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제 입력 1 
5 17
예제 출력 1 
4
*/

#include <iostream>
#include <map>
#include <queue>
using namespace std;

class Node
{
public:
	int _visitsec;
	int _prevN;
	Node(int sec, int prev) : _visitsec(sec), _prevN(prev)
	{
		
	}
};

int main()
{
	queue<int> q;
	map<int, Node*> visit; // <위치,노드>
	int N, K; // N = 수빈이   K = 동생
	cin >> N;
	cin >> K;
	if (N == K)
	{
		cout << 0 << endl;
		return 0;
	}
	q.push(N);
	visit[N] =new Node(0, 0);
	while (true)
	{
		if (q.empty()) break;
		int n = q.front();
		//cout << n << endl;
		if (n == K)
		{
			cout << visit[n]->_visitsec << endl;
			break;
		}
		if (n*2 <= K)
		{
			q.push(n * 2);
			visit[n*2] =new Node(visit[n]->_visitsec+1, n);
			q.pop();
			continue;
		}

		if (visit[n - 1] == NULL)
		{
			q.push(n - 1);
			visit[n - 1] = new Node(visit[n]->_visitsec + 1, n);
		}

		if (visit[n + 1] == NULL)
		{
			q.push(n + 1);
			visit[n + 1] = new Node(visit[n]->_visitsec + 1, n);
		}

		if (visit[n * 2] == NULL && n < K)
		{
			if (K-n > K-n*2 || K-n > n*2-K)
			{
				q.push(n * 2);
				visit[n * 2] = new Node(visit[n]->_visitsec + 1, n);
			}
		}
		q.pop();
	}
	return 0;
}

rational331 4년 전 1

반례 찾았습니다.

/* 
TEST CASE #1:
6 16
exp -> 3
you -> 6

TEST CASE #2:
8 20
exp -> 3
you -> 5

TEST CASE #3:
15964 89498
exp -> 4781
you -> 19110

*/

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

문제

문제

출처

ICPC

반례 부탁드립니다.

shapins 4년 전 0

rational331 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말