정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.
- 2를 곱한다.
- 1을 수의 가장 오른쪽에 추가한다.
A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.
입력
첫째 줄에 A, B (1 ≤ A < B ≤ 10^9)가 주어진다.
출력
A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.
예제 입력 1
2 162 |
예제 출력 1
5 |
2 → 4 → 8 → 81 → 162
예제 입력 2
4 42 |
예제 출력 2
-1 |
예제 입력 3
100 40021 |
예제 출력 3
5 |
100 → 200 → 2001 → 4002 → 40021
더보기
Solution
#include<stdio.h>
int main(void)
{
int A, B, count=0;
scanf("%d%d", &A, &B);
while(A<B)
{
if(B%2==0)
B/=2;
else if(B%10==1)
B/=10;
else
break;
count++;
}
printf("%d\n", A==B?count+1:-1);
return 0;
}
728x90
'백준 알고리즘' 카테고리의 다른 글
<백준 알고리즘> 11725번: 트리의 부모 찾기 (0) | 2023.02.09 |
---|---|
<백준 알고리즘> 12865번: 평범한 배낭 (0) | 2023.02.09 |
<백준 알고리즘> 17298번: 오큰수 (0) | 2023.02.08 |
<백준 알고리즘> 15665번: N과 M (11) (0) | 2023.02.08 |
<백준 알고리즘> 15663번: N과 M (9) (0) | 2023.02.08 |