728x90
문제
정수 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 |
댓글