[알고리즘] 백준 파이썬 25418 정수 a를 k로 만들기

📍 문제 탐색하기

양의 정수 A에서 K로 변경하는 최소 연산 횟수를 구하는 문제입니다.
사용할 수 있는 연산은 다음 두 가지입니다:

1. 연산 1: 현재 수에 1을 더한다. → A=A+1
2. 연산 2: 현재 수에 2를 곱한다. → A=A×2

목표:
정수 A에서 시작하여 K로 만들기 위한 최소 연산 횟수를 출력한다.

---

문제 조건

• 1≤A<K≤1,000,000
• 최소 연산 횟수를 찾기 위해 최적의 경로 탐색이 필요함.
• 연산이 빠르게 수행되도록 효율적인 방법 필요.

---

가능 시간 복잡도

• 완전 탐색(브루트포스): O(2^N) → 시간 초과 가능성.
• BFS(너비 우선 탐색): O(N) → 최적해 보장.
• 역방향 탐색(탑다운 방식): O(log⁡N) → 효율적인 방식.

---

📍 코드 설계하기

이 문제를 해결하기 위해 탑다운 방식(역방향 탐색)을 적용했다.
K에서 A로 거꾸로 접근하여 연산 횟수를 줄이는 전략을 선택했다.

알고리즘 아이디어

1. K가 A보다 크면 반복:
   • K가 짝수이면 2로 나눔.
   • K가 홀수이면 1을 빼서 짝수로 만듦.
   • 연산 횟수 증가.
2. A와 같아지면 종료.

---

📍 코드 구현

import sys
input = sys.stdin.readline

A, K = map(int, input().split())
cnt = 0

while K > A:
    if K % 2 == 0:
        if K // 2 < A:
            K = K - 1   
        else :
            K = K // 2 
    else:
        K = K -1
    cnt += 1
    
print(cnt)