[백준][16953번: A -> B]

문제

문제링크

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

• 2를 곱한다.
• 1을 수의 가장 오른쪽에 추가한다.
  A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

입력

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

출력

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

접근방법

조건은 나누어서 접근했다.
조건1. 일의 자리가 1일 때
조건2. 일의 자리가 1이 아니고 2로 나누어질 때
될 수 없는 조건 1. B가 A보다 작아질 때
될 수 없는 조건 2. 일의 자리가 1이 아니고 2로도 나누어 떨어지지 않을 때

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        String A = (st.nextToken());
        String B = (st.nextToken());
        int count=1;
        while(!B.equals(A)){ // A와 B가 같아지면 종료
            if(Integer.parseInt(B) < Integer.parseInt(A)){ //B가 A보다 작아지면 만들어질 수 없음
                count = -1;
                break;
            }
            if(B.charAt(B.length()-1)!='1' && Integer.parseInt(B)%2!=0){ // 2로 나누어지지도 끝이 1이 아니면 만들어질 수 없음
                count = -1;
                break;
            }
            if(B.charAt(B.length()-1)=='1'){ //  1을 제거한다.
                B = B.substring(0,B.length()-1);
            }else{ //  2를 나눈다
                int temp = Integer.parseInt(B);
                temp /= 2;
                B = Integer.toString(temp);
            }
            count++;
        }
        System.out.println(count);
    }
}

알고 넘어가기

substring
문자열 String을 쪼개고 싶을 때 주로 사용한다.
사용법
1. substring(startIndex) -> startIndex부터 문자열 끝까지 짜른다.
2. subString(startIndex,endIndex) -> startIndex부터 endIndex전까지 짜른다.
ex) String str = apple;
1. substring(2) -> ple
2. substring(1,3) -> pp