[백준 16953] A → B (C#, C++) - soo:bak

문제 링크

16953번 - A → B

설명

정수 A를 B로 바꾸는데, 2를 곱하거나 오른쪽에 1을 붙이는 연산만 사용할 수 있습니다. 최소 연산 횟수를 구하는 문제입니다.

접근법

A에서 B로 정방향 탐색하면 매 단계마다 2를 곱할지, 1을 붙일지 두 가지 선택이 있어 경우의 수가 많아집니다. 반대로 B에서 A로 역추적하면 각 단계에서 선택이 하나로 정해집니다.

B가 1로 끝나면 마지막 연산이 1을 붙인 것이므로 1을 떼면 됩니다. B가 짝수면 마지막 연산이 2를 곱한 것이므로 2로 나누면 됩니다. 둘 다 해당하지 않으면 A에서 B로 만들 수 없는 경우입니다.

B가 A보다 클 동안 위 과정을 반복하며 연산 횟수를 세고, B가 정확히 A가 되면 횟수에 1을 더해 출력합니다. B가 A보다 작아지면 불가능하므로 -1을 출력합니다.

---

Code

C#

using System;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var parts = Array.ConvertAll(Console.ReadLine()!.Split(), long.Parse);
      var a = parts[0];
      var b = parts[1];
      var cnt = 0;

      while (b > a) {
        if (b % 10 == 1)
          b /= 10;
        else if (b % 2 == 0)
          b /= 2;
        else
          break;
        cnt++;
      }

      if (b == a)
        Console.WriteLine(cnt + 1);
      else
        Console.WriteLine(-1);
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  ll a, b; cin >> a >> b;
  int cnt = 0;
  while (b > a) {
    if (b % 10 == 1)
      b /= 10;
    else if (b % 2 == 0)
      b /= 2;
    else
      break;
    cnt++;
  }

  if (b == a)
    cout << cnt + 1 << "\n";
  else
    cout << -1 << "\n";

  return 0;
}