문제 URL : www.acmicpc.net/problem/16953
16953번: A → B
첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.
www.acmicpc.net
문제접근법 : 간단한 BFS 문제입니다. 숫자가 지속적으로 증가하니 int형 범위를 초과할지도 몰라 long long으로
계산해서 풀었습니다. 코드만 보면 바로 이해하실거니 문제가 어렵지않아 바로 이해하실거라 봅니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
//By 콩순이냉장고
#include <iostream> #include <vector>
#include <queue>
#include <unordered_set>
using namespace std;
long long a, b;
int bfs(){
unordered_set<long long> visit;
queue<pair<long long,int>> q;
q.push({ a, 1 });
visit.insert(a);
while (!q.empty()){
long long cur = q.front().first;
int cnt = q.front().second;
q.pop();
if (cur == b){
return cnt;
}
long long next = cur << 1;
if (1<=next&&next<=b&&visit.count(next) == 0){
visit.insert(next);
q.push({ next, cnt + 1 });
}
next = 1L + cur * 10L;
if (1 <= next&&next <= b&&visit.count(next) == 0)
{
visit.insert(next);
q.push({ next, cnt + 1 });
}
}
return -1;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
cin >> a >> b;
cout << bfs() << "\n";
}
|
cs |
궁금한점 혹은 모르는점 언제든 댓글 부탁드립니다.
'백준' 카테고리의 다른 글
| 백준 9944 NxM 보드 완주하기 (0) | 2020.12.31 |
|---|---|
| 백준 12931 두 배 더하기 (0) | 2020.12.31 |
| 백준 1107 리모컨 (0) | 2020.11.29 |
| 백준 16562 친구비 (0) | 2020.10.02 |
| 백준 10216 Count Circle Groups (0) | 2020.10.02 |
