[알고리즘] 백준 16953번: A → B (C++), 당신 1억 맞죠? 아뇨 사람 잘못 보셨는데요

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

16953번: A → B

이번 문제는 어떤 특이한 응용력 혹은 논리력이라기보다 수를 잘못 읽어서 발생한 문제에 대해 포스팅한다.

 

문제는 크게 어렵지 않다. BFS를 돌려서 기존 value에 2를 곱한 것과 value의 뒷자리에 1을 붙여주고, 큐를 돌려서 찾는 값(findValue)이 나오면 종료시켜서 얼마나 걸렸는지 출력하면 되는 문제다.

 

오류는 10^9를 10억이 아닌 1억으로 봐서 생긴 문제였다.

뒷자리에 1을 넣을 때 value에 10을 곱하고, 1을 더해주기 때문에 1억이 넘으면 안 되기 때문에 조건에 1천만을 안 넘는 value를 다음 기능을 수행하게 해주었다.

하지만, 10억이기 때문에 1억을 조건으로 달아주어야 하는 점...

헷갈리지 말자..^^

 

[AC 코드]

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

int a, b;

int bfs(int value, int findValue) {
	queue<pair<int, int>> q;
	q.push(make_pair(value, 1));
	while (!q.empty()) {
		int front = q.front().first;
		int frontOper = q.front().second;

		//cout << front << ' ';
		if (front == findValue) {
			return frontOper;
		}

		q.pop();

		if (front <= 100000000) {
			int v1 = front * 10 + 1;
			if (v1 <= findValue) {
				q.push(make_pair(v1, frontOper + 1));
			}
		}
			int v2 = front * 2;
			if (v2 <= findValue) {
				q.push(make_pair(v2, frontOper + 1));
			}
	}
	return -1;
}

int main() {
	cin >> a >> b;
	cout << bfs(a, b);
	return 0;
}