BOJ - A->B 16953번 (JAVA)

❓ 문제 - 백준 A->B 16953번 - JAVA 풀이법

 

출처 

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

16953번: A → B

 

 

📝 문제해결법

1. 이 문제는 Greedy(탐욕법)으로 알고리즘을 풀었다.

• A->B를 만들기 위해 여러 가지 경우(BFS or DFS)를 고려하기엔 A, B의 범위가 10^9 이므로 풀 수 없다.
• 따라서 while 문을 돌면서 B->A를 만들 수 있는지 체크하면서 카운트를 해준다.
• B는 항상 A보다 커야하며 B가 작아지면 A를 만들 수 없으므로 break로 빠져나온 후 -1을 출력한다.
• B는 항상 A에서 두 가지 경우(2를 곱하거나, 1의 수를 가장 오른쪽에 추가)해서 만들어진 수므로, 우선 2로 나누어지지 않거나 맨 끝수가 1이 아니라면 A가 될 수 없기에 -1을 출력한다.
• 만약 끝 수가 1이라면 끝수를 뺀 상태로 B를 변경하고, B가 짝수라면 2로 나눠준다.
• 계속 while을 돌면서 해당 조건에 따라 B가 A가 같아지면 while을 빠져나오고 정답을 출력한다.

 

2. 문제를 풀면서 느낀점

• B->A로 수를 만들어가면서 하는 방법은 떠올렸지만... B는 무조건(끝 수가1이거나 2로 나누어지는 수)라는 것은 다른 사람의 풀이를 보면서 깨달았다..
• 그리디 많이 풀자 ^_^.... 

 

 

💻 소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String[] s = br.readLine().split(" ");
		int a = Integer.parseInt(s[0]);
		int b = Integer.parseInt(s[1]);

		int ans = 0;
		while(a!=b) {
			if(b < a) {
				ans = -1;
				break;
			}
			
			if(b%2 != 0 && b%10 != 1) {
				ans = -1;
				break;
			} 


			if(b%10 == 1) {
				ans++;
				b = (b/10);
			}
			else if(b%2 == 0){
				ans++;
				b /= 2;
			}
			
			
		}
		if(ans != -1) {
		bw.write(String.valueOf(ans+1));
		} else {
			bw.write(String.valueOf(ans));
		}
		bw.flush();
		bw.close();
		
	}

}