백준 13549 숨바꼭질 3
이 문제는 숨바꼭질1 문제와 달리 원래 거리에서 2배를 해서 0초 안에 갈 수 있다. 이 숨바꼭질 문제들은 이동하는 순서에 따라 답이 틀려지게 된다.
숨바꼭질1에서는 2배를 해서 갈 때, 1초가 걸린다. 그래서 n과 k에 0과 2가 입력 됐을 때, cur2 , cur+1 ,cur-1 순서라면 0 -> 0 -> 1 -> 2로 답이 3이 나오고 cur+1 ,cur2 ,cur-1 순서라면 0 -> 1-> 2로 답이 2가 나온다. 이렇게 순서에 따라 답이 다르게 도출된다.
숨바꼭질3에서는 cur*2 , cur-1 ,cur+1 순서가 되어야 한다.
ex)
for문에서 cur2 , cur+1 ,cur-1 순서 일 때
4 6 => 4 -> 5 -> 6
답 : 2
for문에서 cur2 , cur-1 ,cur+1 순서 일 때
4 6 => 4 -> 3 -> 6
답 : 1
#include<bits/stdc++.h>
#define INF 987654321
using namespace std;
int n, k;
int vis[100001];
queue<int> q;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> k;
fill(vis, vis + 100001, -1);
q.push(n);
vis[n] = 0;
while (!q.empty()) {
int cur = q.front();
q.pop();
if (cur == k) break;
for (int i = 0; i < 3; i++) {
if (i == 0) {
int nxt = cur * 2;
if (nxt < 0 || nxt>100000) continue;
if (vis[nxt]<0) {
vis[nxt] = vis[cur];
q.push(nxt);
}
}
else {
int nxt;
if (i == 1) {
nxt = cur - 1;
}
else {
nxt = cur + 1;
}
if (nxt < 0 || nxt>100000) continue;
if (vis[nxt]<0) {
vis[nxt] = vis[cur]+1;
q.push(nxt);
}
}
}
}
cout << vis[k] << '\n';
}
Author And Source
이 문제에 관하여(백준 13549 숨바꼭질 3), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@supway/백준-13549저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)