#4 - 16953번 A → B

문제

정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.

• 2를 곱한다.
• 1을 수의 가장 오른쪽에 추가한다. 

A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

입력

첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.

출력

A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.

내 풀이

A는 int, B는 string으로 받는다. B의 끝자리가 1로 끝나면 1을 제거해 주고, B가 짝수라면 2로 나누고 B를 갱신한다. 그리고 B가 1이 아닌 다른 홀수로 끝날 때에는 그냥 -1을 출력한다.

 

 

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

#include <iostream> #include <string> using namespace std;   int main() {     int A;     string B;     cin >> A >> B;       int n = stoi(B);     int count = 1;       while (A < n) {           if (B.back() == '1') {             B.pop_back();             n = stoi(B);             count++;         }         else if (n % 2 == 0) {             n = n / 2;             B = to_string(n);             count++;         }         else             break;     }       if (A == n)         cout << count;     else         cout << -1;       return 0; }

cs