[백준] 16953번 A -> B C++ 풀이16953번 A -> B C++ 풀이

---

알고리즘 분류

• 그래프 이론
• 그리디 알고리즘
• BFS
• DFS

---

문제 설명

정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.

• 2를 곱한다.
• 1을 수의 가장 오른쪽에 추가한다. 

A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

---

입력 설명

첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.

---

출력 설명

A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.

---

예제 입력

2 162

4 42

100 40021

---

예제 출력

5

-1

5

---

아이디어

queue에 현재 값과 count를 저장하면서 b에 도달할 때까지 BFS를 돌린다. 찾으면 count 못 찾으면 -1을 출력한다.

---

알고리즘

queue에 pair<long long,int>를 넣어서 first는 현재 값을 저장하고 second는 지금까지 몇 단계를 거쳤는지 count를 저장한다.

그리고 현재 값 * 2 나 현재 값 * 10 + 1한 값이 1 이상 b이하이면 해당 값을 queue에 넣는다.

만약 q의 front에서 뽑아낸 값이 b와 일치한다면 그 때의 count를 출력한다.

만약 일치하는 값이 q가 모두 빌 때까지 없다면 -1을 출력한다.

---

코드

#include <iostream>
#include <queue>
using namespace std;
int main()
{
	int a,b;
	cin>>a>>b;
	queue<pair<long long,int>> q;
	q.push({a,1});
	while(!q.empty())
	{
		long long start = q.front().first;
		int cnt = q.front().second;
		q.pop();
		if(start == b) {
			cout<<cnt;
			return 0;
		}
		if(0 < start * 2 && start * 2 <= b)
			q.push({start * 2, cnt+1});

		if(0 < start * 10 + 1 && start * 10 + 1 <= b)
			q.push({start * 10 + 1, cnt+1});
	}
	cout<<-1;
	return 0;
}

---

후기

문제 링크 -> https://www.acmicpc.net/problem/16953

처음에는 visited  배열에 count를 저장하는 단순한 방법으로 가려고 했는데 배열의 크기를

설정하는데 자꾸 out of bound error가 발생했다.

그래서 배열을 사용하지 않고 queue에 pair를 넣는 방법으로 바꿔서 해결했다.

그리고 현재 값을 저장하는 자료형은 long long을 사용해야한다.

왜냐하면 현재 값에 * 10 + 1을 하는 계산이 발생할 때 이 값이 int 범위를 넘어설 수 있기 때문이다.

---

본 블로그의 모든 글은 개인적인 학습 내용이므로 다양한 오류가 있을 수 있습니다.

오류를 발견하신다면 해당 내용 댓글로 알려주시면 감사하겠습니다!