[JAVA][BOJ][S2] 16953. A->B

16953번: A → B

문제

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

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

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

입력

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

출력

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

풀이

두 가지 방법을 이용해 풀었다 첨부한 코드가 차례로 1번, 2번 풀이다

1. bfs를 이용해 A->B로 연산의 최솟값 구하기

2. B->A로 조건문을 사용해 가능한 값 구하기

코드

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

public class S2_16953_AB {

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int ans = bfs(n, m, 0);
        
        System.out.println(ans);
    }

	private static int bfs(long n, long m, int cnt) {
		Queue<Long> queue = new LinkedList<>();
        queue.add(n);

        while(!queue.isEmpty()){
            int size = queue.size();

            for(int i=0; i < size; i++){
                long tmp = queue.poll();
                if(tmp==m) return cnt+1;
                if(tmp*2<=m) queue.add(tmp*2);
                if(tmp*10+1<=m) queue.add(tmp*10+1);
            }
            cnt++;
        }
        return -1;
	}
}

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

public class S2_16953_AB2 {

    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 ans = 1;
        
        while(B!=A) {
        	if(B<A || (B%10 != 1 && B%2 != 0)) {
        		ans = -1;
        		break;
        	}
        	
        	if(B%10 == 1) B /= 10;
        	else if(B%2 == 0) B /= 2;
        	
        	ans++;
        }
        
        System.out.println(ans);
        
    }

}

결과

아래가 1번, 위가 2번 풀이다

 

#자바 #java #boj #백준 #알고리즘