Greedy_12_A->B(16953)

문제

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

2를 곱한다.
1을 수의 가장 오른쪽에 추가한다.
A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

입력

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

출력

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

풀이

• 조건식 돌때마다 cnt 값 누적
• B 가 A와 같아져야 한다. B의 끝수가 1일땐 [-1]인덱스만 빼고 string 을 재 초기화
• B 가 2로 나뉘어 떨어질 땐 B를 2로나눈 몫으로 초기화
• B의 끝수가 홀수라 나뉘어 질 수 없을때는 -1 출력, 시스템 종료
• B가 A보다 작아지면 어떤 계산으로든 A와 같아질 수 없으므로 -1 출력, 시스템 종료

---

따라서 조건은 아래와 같다
while 문을 돌린다 조건은 A와 B가같은 경우 종료
같아지려는 수보다 작아진 경우 if int(B) < int(A):exit()
끝이 1인 경우 string 초기화 elif int(B[-1]) == 1:B = str(int(B) // 2)
2로 나뉘어지는 경우 B를 몫으로 초기화 elif int(B) % 2 == 0:B = str(int(B) // 2)
그 외 홀수의 경우 2로 나뉘어 질 수 없으므로 종료else: exit()

코드

import sys
sys.stdin = open("input.txt","rt")

def input():
    return sys.stdin.readline().rstrip()


A, B = input().split()
cnt = 1

while B != A:
    #같아지려는 수보다 작아진 경우
    if int(B) < int(A):
        print(-1)
        exit()

    elif int(B[-1]) == 1:
        cnt+=1
        # 맨 뒤 값 뺀 수로 초기화
        B = B[:len(B)-1]

    elif int(B) % 2 == 0:
        cnt+=1
        B = str(int(B) // 2)
    
    else:
        print(-1)
        exit()

print(cnt)

배운 것

str 을 [n:m] 으로 slice 할 수 있구나

코멘트

조건식은 항상 else 의 경우도 생각해라

시간초과 난 이유, else를 잡지 못했기 때문