[TIL] 백준 25418 - 정수 a를 k로 만들기 ( python )

📌 문제 탐색하기

A, K : 양의 정수

 

조건

• 연산 1: A에 1을 더한다.
• 연산 2: A에 2를 곱한다.

위의 조건을 반복적으로 적용하여 A를 K로 만드는 최소 연산 횟수를 구하는 것이 핵심입니다.

 

1 ≤ A < K ≤ 1,000,000

가능한 시간복잡도

1. A부터 조건 탐색
   
   • A에서부터 연산을 적용한 결과들을 차례대로 탐색하면서 최소 횟수로 K에 도달하는 경로를 찾습니다.
   • K와 A의 차이가 커질수록, A가 작고 K가 1,000,000에 가까운 경우에는 탐색해야 할 상태의 수가 많아집니다.
   • 최악의 경우 O(K - A) 이상의 노드를 탐색할 수 있습니다.
2. K부터 조건 탐색
   
   • K가 항상 A보다 큰 값이기 때문에 분할 연산을 적용할 수 있는 경우가 많습니다.
   • 여러 번 K를 절반으로 줄여 빠르게 A에 접근할 수 있습니다.
   • K가 지수적으로 감소하여 총 연산 횟수가 대략 O(log K)가 됩니다.

알고리즘 선택

K에서 A로 내려가는 역연산은 K에서 1을 빼거나 2로 나누는 방식으로 단순하게 진행됩니다.
각 단계에서 어떤 연산이 최적일지 결정하기가 더 명확하기 때문에 역연산으로 접근해 보겠습니다.

---

📌 코드 설계하기

• 문제의 Input을 받습니다.
• 연산 횟수를 세기 위한 count 변수를 0으로 초기화합니다.
• 최솟값을 구하기 위해 반복문을 반복합니다
  
  • 만약 K가 짝수이고, K // 2가 A보다 크거나 같을 경우 
    • K = K // 2
  • 그 외의 경우( K가 홀수이거나, 짝수지만 K // 2가 A보다 작을 경우 )
    • K = K - 1
  • count 값을 1 증가합니다.
  • A == K 일 때, 루프 종료합니다.
• count 값을 출력하여 최소 연산 횟수를 출력합니다.

---

📌 시도 회차 수정 사항 (Optional)

• 1회차 : 단순히 K가 홀수면 1 빼고, 짝수면 무조건 2로 나누는 코드로 작성
  • 짝수인 경우 K를 2로 나누면 A보다 작아지는 상황이 발생했습니다.
• 2회차 : 짝수인 경우, K를 2로 나누기 전에 “K // 2가 A보다 큰지”를 확인하는 조건을 추가
  • 조건문에서 A와 K가 정확히 같을 때의 경우를 제대로 처리하지 못했습니다.

---

📌 정답 코드

import sys
input = sys.stdin.readline

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

while True:

    if K % 2 == 0 and K // 2 >= A:
        K = K // 2
    else:
        K = K - 1

    count += 1

    if A == K:
        break

print(count)