글 읽기 - C++ / 80퍼까지 채점 진행하다가 틀렸다고 하네요... 틀린지 모르겠어요..

haeul 5년 전 0

알려주세요..

------------------------------------------------------------------------

//boj 1697 숨바꼭질

/*
수빈이 위치 : N (0<= N <=100,000)
동생   위치 : K (0<= K <=100,000)

수빈이 => 걷거나 순간이동 가능

걷는다 => 1초 후에 X - 1 또는 X + 1로 이동
순간이동 => 1초 후에 2*X의 위치로 이동

수빈이가 동생을 찾을 수 있는 가장 빠른 시간

*/

#include<iostream>
#include<cstring>
#include<queue>

using namespace std;

int N, K;
int visit[100001];

int BFS()
{
	queue<pair<int,int>> q;

	q.push(make_pair(N, 0));
	visit[N] = 1;

	int a;
	int b;

	while (!q.empty())
	{
		a = q.front().first;
		b = q.front().second;
		q.pop();

		if (2 * a <= 100000 && a < K && !visit[2 * a])
		{
			q.push(make_pair(2 * a, b + 1));
			visit[2 * a] = 1;
		}
		if (a + 1 <= 100000 && !visit[a + 1])
		{
			q.push(make_pair(a + 1, b + 1));
			visit[a + 1] = 1;
		}
		if (a - 1 >= 0 && !visit[a - 1])
		{
			q.push(make_pair(a - 1, b + 1));
			visit[a - 1] = 1;
		}
		

		if (a + 1 == K || a - 1 == K || 2 * a == K) break;
	}
	return ++b;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin >> N >> K;

	cout << BFS();

	return 0;
}

startlink 5년 전 1

N, K ≤ 100,000 이지만, 위치는 100,000을 넘어갈 수 있겠죠

djm03178 5년 전 1

10만을 넘어가지 않아도 항상 최적해를 찾을 수 있습니다.

문제는 n == k일 때 2가 출력되는 것입니다. 실제로 75%에서 그러한 데이터가 있는 것을 확인했습니다.

haeul 5년 전 0

감사합니다 n==k 일 때 2가 출력되는 문제를 해결해서 맞출 수 있었습니다~~

두 분 다 댓글 달아주셔서 감사합니다!!

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

문제

문제

출처

ICPC

C++ / 80퍼까지 채점 진행하다가 틀렸다고 하네요... 틀린지 모르겠어요..

haeul 5년 전 0

startlink 5년 전 1

djm03178 5년 전 1

haeul 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말