백준 16953번
https://www.acmicpc.net/problem/16953

문제

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

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

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

입력

첫째 줄에 A, B (1 ≤ A < B ≤ 10$^9$

출력

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

예제 입력 1

2 162

2 → 4 → 8 → 81 → 162

4 42

100 40021

100 → 200 → 2001 → 4002 → 40021

예제 출력 1

5

-1

5

생각하기

DFS/BFS와 Greedy 알고리즘 유형의 문제입니다.
조건만 이해를 한다면, 충분히 풀 수 있는 문제였습니다.

조건은 문제에 모두 명시되어 있습니다.

A라는 숫자를 B로 만드는데
가장 뒤에 1을 붙이거나, 2를 곱해서 B로 만드는 것,

동작

저는 반대로 풀었습니다.
A -> B 로 가는 것이 문제였지만, 보통 미로를 풀 때도 출발점에서 도착점으로 가는 건 어렵지만 도착점에서 출발점으로 가는 건 쉽습니다.

이런 것처럼 이 문제도 B -> A로 반대로 가면 조금 더 쉽게 풀 수 있을 것으로 생각했습니다.

그래서 B와 A가 같지 않으면 계속 반복되도록 했고,

탈출 조건은 A==B이면 자동 탈출이고, 예외로는 B보다 A가 커질 경우,
즉 B가 A를 지나칠 경우입니다.

이 경우는 당연히 A와 B는 다르다니까 count = -1로 break 해주면 됩니다.

각 조건은

1. B가 짝수일 경우 2로 나누어주고,

2. 가장 뒤의 숫자가 1일 경우 1을 제거

3. B가 홀수가 될 경우 2로 나눌 수 없으므로 바로 count = - 1 로 break를 해주면 됩니다.

BFS도 크게 다르지 않습니다. Queue를 사용해서 구현하여

탈출조건을 Greedy알고리즘에서 사용한 조건으로 만들어주면 됩니다.

TMI

DFS/BFS문제인데, 왜 자꾸 다른방법으로 풀게되지?
괜찮은건가?

코드

Greedy

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		long A = Long.parseLong(st.nextToken());
		long B = Long.parseLong(st.nextToken());		
		int count = 1;

		while(B != A) {
			String str = Long.toString(B);	

			if(B % 2 == 0) {
				B /= 2;
			}
			else if(str.charAt(str.length() -1) == '1') {
				B = Long.parseLong( str.substring(0, str.length() - 1) );
			}
			else {
				count = -1;
				break;
			}

			if(B < A) {
				count = -1;
				break;
			}

			count ++;
		}		

		System.out.println(count);
	} // End of main
} // End of class

BFS

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

public class Main {
	static Queue<Long> que = new LinkedList<>();		

	static long A, B;
	static int count = 1;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		A = Long.parseLong(st.nextToken());
		B = Long.parseLong(st.nextToken());		

		BFS();
		System.out.println(count);

	}

	static void BFS() {
		que.offer(B);

		while( !que.isEmpty() ) {
			long num = que.poll();
			String str = Long.toString(num);	

            if(num == A) {
				return;
			}
			else if(num < A) {
				count = -1;
				return;
			}

	
			if(num % 2 == 0) {
				num /= 2;
				que.offer(num);
				count ++;
			}
			else if(str.charAt(str.length() -1) == '1') {
				num = Long.parseLong( str.substring(0, str.length() - 1) );
				que.offer(num);
				count ++;
			}
			else {
				count = -1;
				return;
			}

		}

	} // End of BFS

} // End of class