[Python] 백준 25418 정수 a를 k로 만들기

🧑‍💻 [Python] 백준 25418 정수 a를 k로 만들기

Silver 3 - 그리디

 

A에서 K를 찾는 것이 아닌, K에서 A를 찾는 것이 제일 쉽다

제일 큰 수에서, 짝수이면 2를 나누고, 홀수이면 1을 빼준다

• 단 짝수에서 2를 나눴을 때에 항상 A보다 커야 한다

---

 

문제풀이

• K를 A로 만들어야 하고, 2로 최대한 많이 나누어야지, 최소로 연산을 할 수 있다
• while 문을 통해 K가 A가 될때까지 순회를 한다
• K가 짝수이거나, 2로 나누었을 때 A보다 커야지만 2로 나눌 수 있다
• 그게 아니고, 홀수이거나 K를 2로 나누었는데, A보다 작으면 계속 1로 빼준

---

 

코드

end, start = map(int, input().split())
count = 0

while start != end:
    if start % 2 == 0 and start // 2 >= end:
        start //= 2
        count += 1
    else:
        start -= 1
        count += 1

print(count)