[C++] 백준 17071 숨바꼭질 5

https://www.acmicpc.net/problem/17071

17071번: 숨바꼭질 5

 

문제 해결

• 1초마다 수빈과 동생은 움직인다.
• 수빈은 1초마다 x-1, x+1 만큼 움직이거나 2*x만큼 순간이동 할 수 있다.
• 동생은 t초에 t만큼 움직인다.
• 수빈은 짝수 t초에 있던 지점을 그 이후 짝수 시간 때에 그 지점에 다시 올 수 있다. 홀수 t에 있던 지점은 그 이후 홀수 시간 때에 대사 올 수 있다.
• 따라서 visited[i][j]에 수빈이 지점 i에 (j=0 짝수시간 때일 때, j=1 홀수시간 때일 때) 최초 도달 시간을 기록한다.
• 후에 동생의 움직임을 보면서 동생이 t초에 'sister'만큼 움직였을 때 수빈이 sister에 최초 도달 시간 visited[sister][t%2]가 t보다 작으면 t초에 만날 수 있는 것이다.

 

CODE

#include <iostream>
#include <queue>
#include <cstring>
#define MAX 500000
using namespace std;

int n, k;
int visited[MAX + 1][2];

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

void Subin() {
	memset(visited, -1, sizeof(visited));
	queue<pair<int, int>>que;
	que.push({ n,0 });
	while (!que.empty()) {
		int now = que.front().first;
		int time = que.front().second;
		que.pop();

		if (0 <= now && now <= MAX) {
			if (visited[now][time % 2] != -1) continue;
			visited[now][time % 2] = time;
			que.push({ now * 2, time + 1 });
			que.push({ now - 1, time + 1 });
			que.push({ now + 1,time + 1 });
		}
	}
}

void Sister() {
	for (register int t = 0; t < MAX; t++) {
		int sister = k + getSum(t);
		if (sister > MAX) break;
		if (visited[sister][t % 2] != -1 && visited[sister][t % 2] <= t) {
			cout << t;
			return;
		}
	}
	cout << "-1";
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> k;
	
	Subin();
	Sister();
}