백준 17071번: 숨바꼭질 5
숨바꼭질 5
아이디어
동생이 도망간다. 숨바꼭질 1~5중에 가장 어렵다. 한번 방문한 위치에 표시하고 이후에 방문하지 않는 방법을 사용하면, 동생이 나중에 거기를 방문히고, 수빈이가 앞으로 갔다 다시 뒤로 와서 만나는 경우를 찾아낼 수 없다. 그렇다고 방문한 위치를 표시하지 않으면 시간초과다. 어떻게 하면 좋을까?
수빈이가 먼저 도달한 곳에 동생이 몇 초 후에 도달한 경우 수빈이가 왕복 1회 즉 2초동안 기다려주면 만날 수 있다. 예를 들어 수빈이가 n초에 도달한 곳에 동생이 n+2, n+4, n+6초에 도달한 경우 둘이 만날 수 있다는 뜻이다.
수빈이와 동생이 둘 다 짝수 초에 도달한 경우와 홀수 초에 도달한 경우를 나눠서 생각하면 문제를 풀 수 있을 것이다.
코드
#include <bits/stdc++.h>
using namespace std;
int N, K;
int visited[2][500001]; // even, odd
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
queue<vector<int>> q;
int n, k, t;
int ans = INT_MAX;
cin >> N >> K;
visited[0][N] = 1;
q.push({N, K, 0});
while (!q.empty()) {
n = q.front()[0];
k = q.front()[1];
t = q.front()[2];
if (n == k){
ans = min(ans, t);
}
if (k > 500000) {
break;
}
if (visited[t%2][k]) {
ans = min(ans, t);
}
q.pop();
if (n+1 <= 500000 && !visited[(t+1)%2][n+1]) {
visited[(t+1)%2][n+1] = visited[t%2][n] + 1;
q.push({n+1, k+t+1, t+1});
}
if (n-1 >= 0 && !visited[(t+1)%2][n-1]) {
visited[(t+1)%2][n-1] = visited[t%2][n] + 1;
q.push({n-1, k+t+1, t+1});
}
if (n*2 <= 500000 && !visited[(t+1)%2][n*2]) {
visited[(t+1)%2][n*2] = visited[t%2][n] + 1;
q.push({n*2, k+t+1, t+1});
}
}
if (ans == INT_MAX) cout << -1;
else cout << ans;
return 0;
}
여담
숨바꼭질 올클 ㄷㄷ vector 말고 tuple을 사용했으면 시간 더 짧았을듯?
Author And Source
이 문제에 관하여(백준 17071번: 숨바꼭질 5), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ks1ksi/백준-17071번-숨바꼭질-5저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)