[백준BOJ] 16953번 A->B.java

 

백준 저지에서 A->B를 자바를 통해 풀어 보았다. 

 

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

16953번: A → B

16953번 A->B.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

16953번 A->B

문제

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

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

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

설명

bfs를 통해 풀 수 있다.

 

A에서 B까지 도달하는 연산의 최솟값을 구해야한다. 이때 2를 곱하거나 연산은 2를 곱하거나, 10을 곱하고 1을 더하는 연산밖에 못 한다. 또한 연산의 최솟값이기 때문에 B를 초과하는 연산에 대해서는 구할 필요가 없다.

 

따라서 연산의 결과가 B보다 같거나 작을 경우에만 연산을 수행한다. 

 

연산과정에서 B를 만나면 바로 출력 후 bfs를 종료한다. 연산의 최솟값이기 때문에 B를 처음 만났을 때가 최솟값이다.

 

모든 연산을 수행하고도 B를 만나지 못하면 -1을 출력한다.

코드

//16953번 A->B.java
package boj20211227;

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

public class A_B_16953 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    
    static class num{
    	long num;
    	int count;
    	num(long num, int count){
    		this.num=num;
    		this.count=count;
    	}
    }
    
    public static void main(String[] args) throws IOException {
    	st = new StringTokenizer(br.readLine()," ");
		int A = Integer.parseInt(st.nextToken());
		int B = Integer.parseInt(st.nextToken());
		
		bfs(A, B);
	}
    
    static void bfs(int A, int B) {
    	Queue<num> q = new LinkedList<num>();
    	q.add(new num(A,1));
    	
    	while(!q.isEmpty()){
    		num now = q.poll();
    		if(now.num==B) {
    			System.out.println(now.count);
    			return;
    		}
    		if(2*now.num<=B)q.add(new num(2*now.num,now.count+1));
    		if(now.num*10+1<=B)q.add(new num(now.num*10+1,now.count+1));
    	}
    	System.out.println(-1);
    }
}