백준 16953 - A -> B

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

16953번: A → B

기본적인 그래프 문제였습니다.

수 A를 입력받아서 B에 도달할 때까지 최소 연산의 수를 구하는 문제입니다.

수는 2배증가 or 뒤에 1붙이기 를 통해서 연산할 수 있습니다.

 

ex) A : 2

     B : 162

     2 -> 4 -> 8 -> 81 -> 162

     이와 같은 방법으로 최소 횟수는 5입니다.

 

1. 주어지는 수의 범위가 10^9이기 때문에 int 범위는 넘습니다. 따라서 long long 형으로 선언해줍니다.

2. 처음에 큐에 (A,0)를 저장해서 BFS를 시작합니다.

3. X*2, X*10+1 각각 B 이하일때까지 횟수를 증가시키면서 큐에 넣습니다.

4, X가 B와 같은 지점이 있다면 횟수를 출력하고 종료합니다.

5. BFS가 끝났는데도 도달하지 못했다면 -1를 출력합니다

 

자세한 것은 코드를 참고해주세요

 

#define CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>

using namespace std;

long long int num, want;
queue<pair<long long int, long long int>> q;


int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> num >> want;
	q.push(make_pair(num, 0));
	while (!q.empty()) {
		long long int x = q.front().first;
		long long int cnt = q.front().second;
		long long int plus_one = x * 10 + 1;
		//cout << x << " " << cnt<< "\n";
		q.pop();
		if (x == want) {
			cout << cnt + 1;
			return 0;
		}
		else {
			if (plus_one <= want) {
				q.push(make_pair(plus_one, cnt + 1));
			}
			if (x*2 <= want) {
				q.push(make_pair(x * 2, cnt + 1));
			}
		}
	}
	cout << "-1";
	return 0;
}

 

질문 및 조언 댓글 남겨주세요