백준 16953번 : A -> B

[레벨4]

 

· 문제

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

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

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

 

· 입력

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

 

· 출력

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

 

 

· 풀이

A -> B로 푸는 순서는 문제가 이해되지 않았는데 B -> A의 순서로 접근하니 이해가 되었다.

 

A < B이고 A-> B일 땐 A에 x2 했으니, B -> A로 바꿀 땐 /2 해준다.

만약 수의 뒷자리가 1이라 나눠 떨어지지 않으면 1을 없애준다.

import java.io.*;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws Exception {
	//자바 입출력 함수 이용. 버퍼에 한번에 데이터를 모아 프로그램에 전송해 입출력 효율을 높일 수 있다.
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //입력값을 하나의 문자열로 받아 여러 토큰으로 분리. 토큰은 분리된 문자열의 부분.
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        //범위가 10의 9제곱이기 때문에 int 대신 long을 써줌.
        long A = Long.parseLong(st.nextToken());
        long B = Long.parseLong(st.nextToken());
        
        //반환할 연산 횟수 저장.
        int cnt = 1;
        
        //A=B일 수 없다.
        while(B != A) {
        	//A>B인 경우 B->A 불가.
        	if(B < A) {
        		cnt = -1;
        		break;
        	}
        	
        	//B의 값을 받을 문자열.
        	String str = String.valueOf(B);
        	
        	//수의 뒷자리가 1이거나 2로 나눠떨어지지 않을 때.
        	if(str.charAt(str.length()-1) != '1' && B % 2 != 0) {
        		cnt = -1;
        		break;
        	}
        	
        	if(B % 2 == 0) {
        		//시프트 연산으로 /2.
        		B >>= 1;
        	} else {
        		//2로 나눠 떨어지지 않으면 처음부터 끝의 앞자리까지의 수만 저장.
        		str = str.substring(0, str.length()-1);
        		B = Long.parseLong(str);
        	}
        	
        	//횟수 증가.
        	cnt++;
        }
        bw.write(cnt + "\n");	//출력.
        bw.flush();	//스트림에 남아 있는 데이터 모두 출력.
        bw.close();	//스트림 닫기.
        br.close();
	}
}