문제
정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.
- 2를 곱한다.
- 1을 수의 가장 오른쪽에 추가한다.
A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.
입력
첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.
출력
A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.
#경우의 수
#뒤에 1만 붙이면 그 값이 되는경우
#1을 붙이고 2를 곱해줘야 하는 경우
#1을 붙이고 2를 곱해주고 다시 1을 붙이는 경우
#만약 B뒤에 1이 있으면 1을 뺴고 그 값이 되는 순간 까지를차즌ㄴ다
#아니면 뒤에 1이 나올때까지 2로 나눈다.
a,b = map(int,input().split())
cnt=1
while b!=a:
#while 끝내는 조건
if a>b:
cnt = -1
break
if b%10 == 1:
b//=10
cnt+=1
else:
if b%2==0:
b//=2
cnt+=1
else:
cnt = -1
break
print(cnt)풀이:
역발상으로 (b에서 a로 가려면 어떻게 해야 되는가)를 생각하니까 쉽게 풀렸다.
b의 끝이 1이면 1을 뒤에서 빼주고, 아니면 2로 나눈다.
- 근데 2로 나눌 때 2로 나눴을 때 나머지가 2인 경우만 나누고, 아니면 애초에 될 수 없는 값이므로 -1을 출력하고 끝낸다. (이 경우의 수를 안 생각해서, 테스트케이스만 돌려보고 처음에 틀렸었음)
간단한 문제지만 잘 접근한 것 같아서 뿌듯하다.
Self Refiner