-
[๋ฐฑ์ค(BOJ) 1697๋ฒ] ์จ๋ฐ๊ผญ์ง (C++)PS(Problem Solving)/C++ 2022. 1. 30. 14:37๋ฐ์ํ
๋ฌธ์ ๋งํฌ
https://www.acmicpc.net/problem/1697
๋ฌธ์ ์ ๋ณด
์ ๋ ฅ
์ฒซ ๋ฒ์งธ ์ค์ ์๋น์ด๊ฐ ์๋ ์์น N๊ณผ ๋์์ด ์๋ ์์น K๊ฐ ์ฃผ์ด์ง๋ค. N๊ณผ K๋ ์ ์์ด๋ค.
์ถ๋ ฅ
์๋น์ด๊ฐ ๋์์ ์ฐพ๋ ๊ฐ์ฅ ๋น ๋ฅธ ์๊ฐ์ ์ถ๋ ฅํ๋ค.
ํ์ด
์ด ๋ฌธ์ ๋ BFS์ ์์ฉ ๋ฌธ์ ๋ก 1์ฐจ์์์์ BFS๋ฅผ ๋๋ฆฌ๋ ๋ฌธ์ ์ด๋ค.
์์ค ์ฝ๋
#include <bits/stdc++.h> using namespace std; #define X first #define Y second int dist[100002]; int n, k; int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> k; fill(dist, dist + 100002, -1); queue<int> Q; Q.push(n); dist[n] = 0; while (!Q.empty()) { auto cur = Q.front(); Q.pop(); for (int nxt : {cur -1, cur + 1, 2 * cur}) { if (nxt < 0 || nxt >= 100002) { continue; } if (dist[nxt] != -1) { continue; } dist[nxt] = dist[cur] + 1; Q.push(nxt); } } cout << dist[k]; return 0; }
๋ฐ์ํ