(백준) 16952번 - A → B

문제

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

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

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

입력

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

 

 

#include <stdio.h>

int main() {
    int a, b, c=1;
    scanf("%d %d", &a, &b);
   while (1) {
     if (a == b) {
       printf("%d\n", c);
         return 0;
       }
       else if (a > b) {
         printf("-1\n");
        return 0;
        }
     
        if (b % 10== 1){
          b /= 10;
          c++;
        }
        else if (b % 2 == 0) {
        b /= 2;
        c++;
        }
         else {
  printf("-1\n");
         return 0;
        }
    }
    return 0;
}

 

1. A, B를 입력받는다.

2. A에서 B를 가는데 할수있는 연산은 2를 곱하거나 A*10+1이다 그러므로 이것을 거꾸로 생각하면 B → A로 가는데는 나머지가 1일때 10을 나누거나 2로 나누어 떨어질때 2로 나누는 방법이 있습니다.

3. 이것을 적용해서 코드를 짜면 while로 무한반복을 해놓고 그 안에서 a=b면 연산 횟수인 c를 출력하고 종료,

4. a>b면 a에서 B로 갈수 없으니까 -1을 출력하고 종료.

5. 만약에 A가 10으로 나눠지거나 2로 나눠지면 나누고 연산 횟수 c에 1을 추가함.

6. 10으로 나누거나 2로 나누는 것도  안되면 -1을 출력하고 종료.