c++ 백준_16953_"A → B"

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

16953번: A → B

 

처음 A 기준으로 BFS를 해볼까 했다.

당연히 시간이 너무 오래걸린다.

​

그래서 B 기준으로 하였다.

B 기준으로 맨 오른쪽에 1이 있다면

1을 지우고,

또는

B 기준으로 2로 나누어 떨어진다면

2를 나누었다.

​

둘 다 해당하지 않는다면 숫자를 만들 수 없다.

​

​

이 방법으로 BFS를 돌렸다.

​

그리고 더 단순하게 할 방법을 찾아서 단순하게 하였다.

​

1. BFS

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

typedef struct {
	int x;
	int cnt;
	int size;
}node;

int main(void) {
	int A, B;

	cin >> A >> B;


	queue<node> q;
	
	int t = 1000000000;

	for (; t >= 1; t /= 10) {
		if (B / t)
			break;
	}

	q.push({ B,1,t });

	while (!q.empty()) {
		int x = q.front().x;
		int cnt = q.front().cnt;
		int size = q.front().size;
		q.pop();

		//cout << x << " , " << size << '\n';
		if (x == A) {
			cout << cnt;
			return 0;
		}

		if (x == 0) {
			cout << -1;
			return 0;
		}

		int rest = 0;
		int temp = x;
		for (int i = size; i > 1; i /= 10) {
			temp %= i;
		}

		if (temp == 1) {
			q.push({ x / 10,cnt + 1, size / 10 });
		}
		if (x % 2 == 0) {
			if (x / 2 < size)
				size/=10;
			q.push({ x / 2, cnt + 1, size });
		}

	}

	cout << -1;
	return 0;
}

 

​

2. 단순

#include <iostream>
#include <vector>
using namespace std;


int main(void) {
	int A, B;

	cin >> A >> B;


	int cnt = 1;

	while (1) {

		if (A == B)
			break;
		
		if (B < A) {
			cout << "-1";
			return 0;
		}

		if (B % 10 == 1) {
			B /= 10;
		}
		else if (B % 2 == 0) {
			B /= 2;
		}
		else {
			cout << "-1";
			return 0;
		}
		cnt++;
	}
	cout << cnt;

	return 0;
}

두 코드다 메모리와 시간이 동일했다.

​

​

​