16953번 : A -> B

https://www.acmicpc.net/problem/16953

16953번: A → B

 

 

문제

 

 

코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int y = sc.nextInt();
        int n=1;

        while(x!=y && y!=0) {
            if(y%2==0) y/=2;
            else if((y-1)%10==0) y=(y-1)/10;
            else break;
            n++;
        }

        if(x!=y) System.out.print(-1);
        else System.out.print(n);
    }
}

 

 

해결방법

문제를 읽어보면 가능한 연산은 2가지가 나온다.

1. y=x*2
2. y=(x*10)+1

A는 1번과 2번의 연산으로 B를 만들어야 한다.

 

거꾸로 생각해보면 B를 1번과 2번의 연산의 반대로 계산하여 A를 만들 수 있다.

1. y/2=x
2. (y-1)/10=x

만약 위의 연산으로 B를 A로 만들 수 없다면 만들 수 없는 수므로 -1을 출력하면 되고 만들어진다면 연산의 횟수를 출력하면 된다. 1번과 2번 연산이 둘 다 가능한 수는 없으므로 조건문을 사용하면 쉽게 판별할 수 있다.

추가적으로 위의 연산으로 B가 0이 되는 경우가 있으므로 while문에 조건을 주고 탈출하여 -1을 출력하도록 하였다.