백준 16953 A -> B C++

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

16953번: A → B

오랜만에 푸는 거라 간단한 문제로 풀어보았습니다.

 

A와 B를 비교할 때 A에 x2 또는 A + "1" 을 하여 B를 몇 번만에 만들 수 있는 지 구하는 문제입니다.

간단하게 bfs를 이용하여 풀었습니다.

A를 x2, +"1" 2가지에 대해 계속 탐색하면서, B와 일치하는 경우가 처음 나오면 그 경우가 답입니다.

x2, +"1" 을 하여도 B보다 작은 경우, 계속 탐색을 이어가고, 그렇지 않으면 탐색을 거기서는 멈춥니다.

 

코드는 다음과 같습니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>

using namespace std;

string doubling(string s) {
	// s를 2배 시키기
	int num = stoi(s);
	num *= 2;
	return to_string(num);
}

string Add(string s) {
	return s + "1";
}

int check(string s1, string s2) {
	// s1 < s2 : 0 => 가능성 있음
	// s1 == s2 : 1 => 정답
	// s1 > s2 : 2 => 진행 안 해도 됨
	if (s1 == s2) {
		return 1;
	}
	else {
		if (s1.size() == s2.size()) {
			if (s1 > s2)
				return 2;
			else
				return 0;
		}
		else if (s1.size() > s2.size()) {
			return 2;
		}
		else if (s1.size() < s2.size()) {
			return 0;
		}
	}
}

int main() {
	
	//  bfs로 비교
	//  비교하다가 제일 먼저 일치하는 순간 나오면 정답
	//  끝까지 없으면 실패

	string a, b;
	cin >> a >> b;

	int result = 0;

	queue< pair<string, int> >q;
	q.push({ a, 0 });

	while (!q.empty()) {
		string s = q.front().first;
		int r = q.front().second;

		q.pop();

		int ret = check(s, b);
		if (ret == 1) {
			result = r;
			break;
		}

		if (ret == 2)
			continue;

		string s2 = doubling(s);
		string s3 = Add(s);

		q.push({ s2, r + 1 });
		q.push({ s3, r + 1 });
	}

	if (result == 0)
		cout << -1;
	else 
		cout << result + 1;
}