[백준 16953] A → B (C++)

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

16953번: A → B

 

1. 주의할 점

- 정수 A는 2*A , 10*A+1 두가지 형태로 바뀔 수 있다.

- A,B의 최댓값이 10억이라서 해당 정수를 방문 했다는 배열을 만들면 안된다.

 

2. 구현

-해당 정수를 방문 했다는 배열을 만들면 안된다 -> Set을 사용한다

이유: A가 2배씩 증가한다고 해도 30개만 들어간다(2^30>10억) + 10*A+1의 경우 그보다 적게 들어간다

 

#include <iostream>
#include <queue>
#include <set>
using namespace std;
struct info {
	long long idx;
	int val;
};
info tmp;
int main() {
	long long start, target, result = -1;
	cin >> start >> target;
	if (start <= target) {
		queue<info> q;
		set<long long> s;
		tmp.idx = start;
		tmp.val = 0;
		q.push(tmp);
		s.insert(start);
		while (!q.empty()) {
			long long cidx = q.front().idx;
			int cv = q.front().val;
			q.pop();
			if (cidx == target) {
				result = cv + 1;
				break;
			}
			if (cidx * 2 <= target && s.find(cidx * 2)==s.end()) {
				tmp.idx = 2 * cidx;
				tmp.val = cv + 1;
				q.push(tmp);
				s.insert(cidx * 2);
			}
			if (cidx * 10 + 1 <= target && s.find(cidx * 10+1) == s.end()) {
				tmp.idx = cidx * 10 + 1;
				tmp.val = cv + 1;
				q.push(tmp);
				s.insert(cidx * 10 + 1);
			}
		}
	}
	cout << result;
	system("pause");
	return 0;
}