[C++] 백준 16953: A → B

문제

[C++] 백준 16953: A → B SILVER 2
https://www.acmicpc.net/problem/16953

 

---

 

접근 방법

백준 16953번은 정수 A를 B로 바꾸는 최소 연산 횟수를 구하는 문제다.
사용할 수 있는 연산은 두 가지뿐이다.

1. 현재 값 × 2
2. 현재 값 뒤에 1을 붙이기 (예: 23 → 231)

이 문제는 연산이 두 갈래로 계속 뻗어나가는 구조이기 때문에 그래프 탐색 문제로 볼 수 있다.

 

각 숫자를 하나의 노드라고 생각하면,

• val → val * 2
• val → val * 10 + 1

이렇게 두 개의 간선이 존재하는 셈이다.

최소 연산 횟수를 구해야 하므로 BFS(너비 우선 탐색) 을 사용했다.

 

상세 아이디어

1. BFS로 최소 횟수 탐색

queue<pair<LL, int>> Q;
Q.push(make_pair(a, 1));  // value, depth

 

• 큐에는 (현재 값, 연산 횟수)를 저장
• 시작 값 A를 depth = 1로 넣는다.
  (문제 조건상 시작도 포함해서 세기 때문에 1부터 시작)

 

2. 두 연산 수행

LL MUL = val * 2;
LL ADD = (val * 10) + 1;

 

• 두 연산 결과를 각각 계산
• 결과가 B 이하일 때만 큐에 추가
  (B를 초과하면 더 이상 의미 없음)

 

3. 목표 도달 시 종료

if (MUL == b)
{
    cout << depth + 1;
    return true;
}

B를 찾는 순간 바로 출력하고 종료한다.
BFS이므로 처음 도달한 순간이 최소 연산 횟수다.

 

구현 시 주의할 점

• 반드시 long long 사용
  • 연산 이 반복되면서 숫자가 매우 커질 수 있다.
    int 범위를 초과할 수 있으므로 반드시 long long(LL) 타입을 사용해야 한다.
• 방문 배열이 필요 없다
  • 이 문제에서는
    • 연산이 항상 값이 증가하는 방향으로만 진행
    • <= b 조건으로 제한
  • 따라서 같은 숫자가 다시 만들어질 일이 없다.
    그래서 별도의 visited 배열이 필요 없다.
• 도달하지 못하면 -1 출력

 

 

---

 

코드

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

typedef long long LL;

bool BFS(int a, int b)
{
	queue<pair<LL, int>> Q;

	Q.push(make_pair(a, 1));  // value, depth

	while (!Q.empty())
	{
		LL val = Q.front().first;
		int depth = Q.front().second;
		Q.pop();

		LL MUL = val * 2;
		LL ADD = (val * 10) + 1;

		if (MUL <= b)
		{
			if (MUL == b)
			{
				cout << depth + 1;
				return true;
			}
			Q.push(make_pair(MUL, depth + 1));
		}
		if (ADD <= b)
		{
			if (ADD == b)
			{
				cout << depth + 1;
				return true;
			}
			Q.push(make_pair(ADD, depth + 1));
		}
	}
	return false;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	LL a = 0, b = 0;
	cin >> a >> b;

	if (!BFS(a, b))
		cout << -1;

	return 0;
}