Algorithm(BOJ)/BFS
[C++] 백준 16935번 - A -> B (BFS)
Nanyoung Kim
2021. 8. 14. 18:57
728x90
문제 링크 : https://www.acmicpc.net/problem/16953
문제
정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.
- 2를 곱한다.
- 1을 수의 가장 오른쪽에 추가한다.
A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.
입력
첫째 줄에 A, B (1 ≤ A < B ≤ 10^9)가 주어진다.
출력
A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.
접근 방법
- BFS를 이용한 완전탐색 문제이며, 자료형에 주의해야하는 문제이다.
- 주어진 입력 값 범위가 1부터 10^9 (십억)인데, 두번째 연산을 할 때 int형 범위가 넘어가므로 a, b 모두 long 형으로 선언해줘야함에 주의하자!
- 두개의 연산 모두 원래의 값보다 증가하는 연산이므로, 연산 후 결과 값이 b를 넘어가면 que에 담지 않는다.
#include <iostream>
#include <queue>
#include <utility>
using namespace std;
int main()
{
long a, b;
cin >> a >> b;
queue<pair<long, long>> que;
que.push(make_pair(a, 0));
long answer = 0;
bool flag = false;
while (!que.empty())
{
long num = que.front().first;
long cnt = que.front().second;
que.pop();
if (num == b)
{
answer = cnt;
flag = true;
break;
}
if(num*2 <= b){
que.push(make_pair(num * 2, cnt + 1));
}
if (num * 10 + 1 <= b){
que.push(make_pair(num * 10 + 1, cnt + 1));
}
}
if (flag)
cout << answer + 1;
else
cout << -1;
}
728x90