BOJ 16953 : A→B

[문제]

1) 정수 A, B가 주어졌을 때, *2 혹은 1을 추가하는 연산을 통해 A->B까지 가는 것이 목표.

2) 이 때,연산의 수행해야하는 연산 횟수의 최솟값을 구해라.

▷ 입력 : A, B (최대 10^9)

 

[풀이]

1) 기본적으로 comma6oz.tistory.com/10 (숨바꼭질) 문제와 탐색방법은 유사하다.

2) bfs로 탐색하고 queue에 현재 노드와 연산 횟수를 저장한다.

   ▷ 현재 노드가 B가 되면 탐색을 종료하고 연산 횟수 반환한다.

3) 숨바꼭질 문제와 다르게 최대값이 매우 크므로 vector를 만들어서 거리 값을 저장하면 메모리 초과가 발생한다.

   ▷ vector을 이용해 BOJ에 제출했을 때 bad_alloc과 OutofBounds가 발생했다.

 

▶ 메모리 초과 해결 방법

   ▷ int 대신 long long 사용

   ▷ 탐색할 다음 노드 (next)를 구하기 전에 next*2와 next*10+1이 최대값을 넘기지 않는지 확인

[코드] c++

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

const long long MAX = 1000000000;
#define X first;
#define Y second;

int main() {
	long long A, B;
	cin >> A >> B;
	
	queue<pair<long long, long long>> q;
	q.push({ A,1 });

	long long ans = -1;

	while (!q.empty()) {
		long long cur = q.front().X;
		long long cnt = q.front().Y;
		q.pop();

		if (cur == B) {
			ans = cnt;
			break;
		}

		long long next;
        //예외처리!!!!!!!!!!!!!!!!!!!!!!!
		if (cur * 2 <= B) {
			next = cur * 2;
			q.push({ next,cnt + 1 });
		}
		if (MAX / 10 >= cur) {
			next = cur * 10 + 1;
			q.push({ next,cnt + 1 });
		}
	}
	cout << ans << "\n";
}