백준 16953_A->B 문제풀이 in C++

2022년 10월 21일 in Devlog on Algorithm

1. 문제 URL
2. 문제 요구사항
3. 접근 방법
4. 풀이 순서
5. 소스코드
6. 문제 풀이 결과

문제 URL

---

https://www.acmicpc.net/problem/16953

문제 요구사항

---

• 정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.
  • 2를 곱한다.
  • 1을 수의 가장 오른쪽에 추가한다.
• A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.
• 첫째 줄에 A, B (1 ≤ A < B ≤ 10^9)가 주어진다.
• A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.

접근 방법

---

• queue에 현재 숫자와 cost를 넣고 문제 조건 연산을 수행하며 값과 cost + 1을 넣으며 수행, 탐색 중 값이 같다면 최솟값과 비교하여 cost가 더 작으면 최솟값 갱신
• 문제에서 주어진 B의 최댓값 안 보고 int형으로 코딩했다 틀렸다.

풀이 순서

---

1. A와 B를 입력 받는다
2. queue에 현재 넘버 A와 cost 0을 넣고 queue가 빌 때까지 BFS 탐색을 수행한다.
3. BFS 수행
   • queue에서 꺼낸 수가 B와 같다면 minimum과 현재 cost를 비교하여 작다면 갱신하도록 한다.
   • 꺼낸 수를 문제의 조건대로 연산하는데 이때, 값이 B 이하라면 queue에 그 값과 cost +1 값을 넣는다.
   • 이와 같은 작업 반복
4. minimum이 MAX 값과 같다면 -1을, 아니라면, minimum을 출력한다.

소스코드

---

#include <iostream>
#include <queue>

using namespace std;

#define MAX 987654321

long long A, B;
long long minimum = MAX;

void input() {
	cin >> A >> B;
}

void solution() {
	queue<pair<int, int>> q;

	q.push({ A, 0 });

	while (!q.empty()) {
		long long now_num = q.front().first;
		long long now_cost = q.front().second;

		q.pop();

		if (now_num == B) {
			if (minimum > now_cost)
				minimum = now_cost;
		}

		if (now_num * 10 + 1 <= B) {
			q.push({ now_num * 10 + 1, now_cost + 1 });
		}
		if (now_num * 2 <= B) {
			q.push({ now_num * 2, now_cost + 1 });
		}
	}

}

void output() {
	if (minimum == MAX)
		cout << -1;
	else
		cout << minimum + 1;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	input();
	solution();
	output();

	return 0;
}

문제 풀이 결과

---