백준 16953번 [A → B](C++)-yes6686- 티스토리

백준 문제 풀이: 16953 [A → B]

---

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

문제 설명:

두 정수 A와 B가 주어졌을 때, A를 B로 바꾸는 연산 횟수의 최솟값을 구하는 문제입니다. 가능한 연산은 다음과 같습니다:

• A에 2를 곱합니다.
• A의 오른쪽에 1을 추가합니다.

연산을 통해 A를 B로 만들 수 없으면 -1을 출력합니다.

입력:

• 첫째 줄에 정수 A와 B가 주어집니다. (1 ≤ A, B ≤ 10⁹)

출력:

• A를 B로 바꾸는 데 필요한 최소 연산 횟수를 출력합니다. 불가능하면 -1을 출력합니다.

---

문제 해결 코드

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

int main() {
    long long A, B;
    cin >> A >> B;

    queue<pair> q;
    q.push({A, 1}); // 초기값과 연산 횟수

    while (!q.empty()) {
        long long current = q.front().first;
        int steps = q.front().second;
        q.pop();

        if (current == B) {
            cout << steps << '\n';
            return 0;
        }

        if (current * 2 <= B) {
            q.push({current * 2, steps + 1});
        }
        if (current * 10 + 1 <= B) {
            q.push({current * 10 + 1, steps + 1});
        }
    }

    cout << -1 << '\n'; // 불가능한 경우
    return 0;
}

예제

입력:
2 162

출력:
5

입력:
4 42

출력:
-1

---

코드 설명

• BFS를 이용한 탐색:
  • 큐를 이용하여 현재 값과 연산 횟수를 저장합니다.
  • 현재 값에서 두 가지 연산(곱하기 2, 10을 곱하고 1 더하기)을 수행합니다.
• 최적화 조건:
  • current * 2와 current * 10 + 1이 B를 넘지 않는 경우에만 연산을 진행합니다.
• 결과 출력:
  • 큐에서 B에 도달하면 연산 횟수를 출력하고 종료합니다.
  • 큐가 비었을 때도 B에 도달하지 못하면 -1을 출력합니다.

시간 복잡도

• BFS 탐색이므로 최악의 경우 연산 횟수는 O(log B)입니다.

---

결과

코드는 BFS를 통해 최소 연산 횟수를 정확히 계산하며, 입력 조건에 따라 불가능한 경우를 올바르게 처리합니다. 효율적인 탐색을 위해 큐를 사용하여 구현되었습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!