백준 17071번 숨바꼭질 5

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 동생은 항상 걷기만 한다. 동생은 항상 매 초마다 이동을 하며, 이동은 가속이 붙는다. 동생이 이동하는 거리는 이전에 이동한 거리보다 1을 더한 만큼 이동한다. 즉, 동생의 처음 위치는 K, 1초가 지난 후 위치는 K+1, 2초가 지난 후 위치는 K+1+2, 3초가 지난 후의 위치는 K+1+2+3이다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 동생을 찾는 위치는 정수 좌표이어야 하고, 수빈이가 0보다 작은 좌표로, 50만보다 큰 좌표로 이동하는 것은 불가능하다.

입력

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

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 수빈이가 동생을 찾을 수 없거나, 찾는 위치가 500,000을 넘는 경우에는 -1을 출력한다.

 

처음에 시간초별로 동생이 갈 수 있는 거리를 배열에 다 저장해 놓고, 수빈이가 매초 탐색하면서 자신의 현재 초에 동생의 위치에 도달할 수 있는가 판단하려 했다만 메모리 초과

그 이유는 수빈이는 +1,-1을 가지고 있어서 중복케이스가 존재하기 때문...

그렇다고 이것을 visit처리로 막으면 +1,-1을 번갈아가면서 수빈이 동생 위치에 도달할 수 있는 케이스가 다 막아짐.

따라서 이에 대한 해결로 수빈이가 어떤 위치에 도달했을 때 짝수 시간에 도착하는가 홀수 시간에 도착하는가로 판단.

짝수 시간에 처음 도착하는 거라면 가령 2초에 14라는 위치에 처음 도달한다면 수빈이는

4,6,8,10,12,,,,,, 2초이후의 모든 짝수초에 14에 도달할 수 있음

따라서 동생이 18초에 14에 도달한다고 하면, 수빈이는 동생과 만날 수 있음. 

대신 조건은 동생이 14에 도달한 시간이 수빈이가 14에 도달한 첫 짝수 초 보다는 이상의 값을 가져야 함.

수빈이가 14라는 위치에 2초만에 처음 도달했는데 동생은 0초에 14에 위치에 있다면 못만남...

 

그리고 visit처리는 따라서 수빈이의 시간초에 대해서 저장해야하고 문제점은 처음 수빈이 위치인 경우에 초가 0이므로

visit에 0을 입력한 후에 동생의 현재 초에 visit가 존재하는가를 파악하려 하면 0초는 없는 것으로 판단하므로

visit를 -1로 세팅하는게 쉬움.

#include<iostream>
#include<string>
#include<vector>
#include<queue>
using namespace std;

int N, K;
int visit[2][500001];

int sum(int n)
{
	return n * (n + 1) / 2;
}

int main(void)
{

	cin >> N >> K;


	queue<pair<int, int> > su;
	su.push({ N,0 });
	visit[0][N] = 0;
	memset(visit, -1, sizeof(visit));

	while (!su.empty())
	{
		int cur = su.front().first;
		int t = su.front().second;
		su.pop();

		if (cur > 500000 || cur < 0)
		{
			continue;
		}

		if (visit[t % 2][cur] != -1)
		{
			continue;
		}

		visit[t % 2][cur] = t;
		su.push({ cur - 1,t + 1 });
		su.push({ cur + 1,t + 1 });
		su.push({ 2 * cur , t + 1 });
	}

	for (int i = 0; i < 500000; i++)
	{
		int nk = K + sum(i);
		if (nk > 500000)
		{
			break;
		}

		if (visit[i % 2][nk] != -1 && visit[i % 2][nk] <= i)
		{
			
			cout << i << endl;
			return 0;
		}
	}
	cout << -1 << endl;

	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}