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

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

16953번: A → B

---

좀 전에 풀었던 문자열 바꾸기와 굉장히 닮은 문제였다

마찬가지로 큰 수를 작은수로 바꿔나가는 편이 좋을 것 같다는 판단

 

 

 

A를 B로 만들기 위해서 두 가지 방법은

1번) 2를 곱하거나, 

2번) 10을 곱하고 1 더하기 (뒷자리에 1을 붙이는것)

이다.

 

10을 곱하고 1더하는 방법이 수를 더 크게 부풀리기 때문에 이 방법을 많이 써야 연산횟수를 줄일 수 있다.

.

.

 

A를 B로 바꾸려고 하면 너무 많은 경우의 수가 생기기 때문에, B를 감소시켜 A로 만들어야 한다.

 

B의 끝자리 숫자가 1이고, 10으로 나눴을 때 A보다 크다면 2번방법을 쓰자.

그렇지 않고 B가 짝수라면 1번방법을 쓰자.

위의 내용에 모두 해당되지 않는다면, 더 이상 할 수 있는 연산이 없으므로 중단한다.

 

---

import java.util.Scanner;

public class P16953 {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		long a = sc.nextLong();
		long b= sc.nextLong();
		long count=0;
		
		
		
		
		if(a>b) {
			System.out.println(-1);
			return;
		}
		while(a<b) {
			
			if(b%10==1 && (b-1)/10 >=a) {
				b=(b-1)/10;
				count++;
			}
			else if (b%2==1) {
				break;
			}
			else {
				b/=2;
				count++;
			}
		}
		
		if(a==b) {
			System.out.println(count+1);
			
		}
		else {
			System.out.println(-1);
		}
		
		
	}

}

큰 숫자가 들어올 것을 대비해 long타입으로 사용했다.