[파이썬/Python] 백준 25418번: 정수 a를 k로 만들기

📌 문제 : 백준 25418번

---

📌 문제 탐색하기

A, K : 변경하려는 수, 원하는 수 $(1 ≤ A < K ≤ 1,000,000)$

A를 K로 변경할 때 사용한 연산의 최소 횟수를 구하는 문제이다.

문제 풀이

처음의 풀이 방식

• while문을 통해 K가 A 될 때까지 짝수면 2로 나누고 홀수면 1을 빼는 연산을 반복하면 된다고 생각했다.
• 홀수, 짝수 여부만으로 연산을 결정해 진행하다보면 영원히 K를 A로 변경하지 못하는 경우가 발생하여 이 부분을 해결해야 했다.

수정한 풀이 방식

• 2로 나누다가 그 값이 A보다 작아지는 경우, K는 영원히 A가 되지 못한다.
• 2로 나눈 값이 A보다 작지 않을 경우에만 나누게 하도록 조건을 추가해 반드시 A가 될 수 있도록 해준다.

가능한 시간복잡도

홀수 연산 → $O(K)$
짝수 연산 → $O(log(𝐾))$

최종 시간복잡도
$O(K)$로 최악의 경우 $O(1,000,000)$가 되는데 이는 1초 내에 연산 가능하다.

알고리즘 선택

조건에 따라 연산 반복하기

---

📌 코드 설계하기

1. 필요한 입력 받기
2. 연산 횟수 변수 정의
3. 반복문 수행
   3-1. K가 A가 될 때까지 연산 반복
   3-2. 짝수면 2 나누기 (반드시 K를 A로 만들 수 있도록 조건 추가)
   3-3. 홀수이면 1 빼기
4. 결과 출력
   
   

---

📌 시도 회차 수정 사항

1회차

while True:
    # K가 A가 될 때까지 연산 반복
    if K == A:
        break

    else:
        # 짝수면 2 나누기
        if K % 2 == 0:
            K //= 2
            # 연산 횟수 세기
            count += 1

        # 홀수이면 1 빼기
        else:
            K -= 1
            # 연산 횟수 세기
            count += 1

• 이와 같이 반복문을 구현했을 때 예제 입력2에서 반복문이 종료되지 않아 출력이 나오지 않는 문제가 발생했다.
• 문제 풀이 항목에서 언급한 것처럼 2로 나눈 값이 A보다 작지 않을 경우만 2로 나누게 하여 해결했다.

---

📌 정답 코드

import sys

input = sys.stdin.readline

# A, K 입력
A, K = map(int, input().split())

# 연산 횟수 변수 정의
count = 0

while True:
    # K가 A가 될 때까지 연산 반복
    if K == A:
        break

    else:
        # 짝수면 2 나누기 (반드시 K를 A로 만들 수 있도록 조건 추가)
        if K % 2 == 0 and K // 2 >= A:
            K //= 2
            # 연산 횟수 세기
            count += 1

        # 홀수이면 1 빼기
        else:
            K -= 1
            # 연산 횟수 세기
            count += 1

# 결과 출력
print(count)

• 결과