본문 바로가기
Algorithm/Baekjoon

Baekjoon 16953 A → B JAVA

by Hunveloper 2022. 3. 6.
728x90
 

16953번: A → B

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

www.acmicpc.net

문제

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

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

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

입력

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

출력

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

풀이

A부터 시작해서 B를 찾는 방법과, B에서 시작해서 A를 찾는 방법으로 풀 수 있는 문제이다.

본인은 B에서 A를 찾는 방법으로 풀었다.

2를 곱해서 마지막자리가 홀수가 나올 수 없으므로 역 역산시 1을 마지막으로 가지면 /10을 해서 2번 연산을 만족하고

1이 아닌 홀수를 1의 자리수로 가지면 그것은 나올 수 없는 값이기에 -1를 출력한다.

코드
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt(), b = sc.nextInt(), cnt=1;		
		while (b>=a) {
			if(b==a) {
				System.out.println(cnt);
				return;
			}
			if(b%10==1)
				b/=10;
			else if(b%2==0)
				b/=2;
			else
				break;
			cnt++;
		}
		System.out.println(-1);
	}
}
728x90
728x90

'Algorithm > Baekjoon' 카테고리의 다른 글

Baekjoon 1966 프린터 큐 JAVA  (0) 2022.03.08
Baekjoon 1874 스택 수열 JAVA  (0) 2022.03.08
Baekjoon 1697 숨바꼭질 JAVA  (0) 2022.03.06
Baekjoon 11726 2×n 타일링 JAVA  (0) 2022.03.06
Baekjoon 11659 구간 합 구하기 4 JAVA  (0) 2022.03.04

댓글