문제 개요
고장 난 계산기가 하나 있다고 가정해 봅시다. 이 계산기는 화면에 표시된 숫자에 대해 단 두 가지 연산만 수행할 수 있습니다.
- 곱하기 2(Double) — 화면의 숫자를 2배로 만듭니다.
- 1 감소(Decrement) — 화면의 숫자에서 1을 뺍니다.
처음에 계산기에는 숫자 X가 표시되어 있습니다. 목표는 화면에 숫자 Y를 표시하기 위해 필요한 최소 연산 횟수를 구하는 것입니다.
예를 들어 입력이 X = 5, Y = 8이라면 정답은 2입니다. 먼저 1을 빼서 4를 만든 뒤, 2배를 하면 8이 되기 때문입니다.
접근 방식: 역방향 그리디
X에서 Y로 직접 탐색하면 경우의 수가 기하급수적으로 늘어나 비효율적입니다. 대신 Y에서 X로 거꾸로 거슬러 올라가면 문제가 훨씬 단순해집니다. 역방향에서 사용할 수 있는 연산은 다음 두 가지뿐입니다.
- Y가 짝수라면 2로 나눈다 (정방향의 '곱하기 2'에 해당)
- Y가 홀수라면 1을 더한다 (정방향의 '1 감소'에 해당)
알고리즘은 다음과 같습니다.
- res := 0 으로 초기화
- Y > X 인 동안 반복:
- res := res + (Y mod 2) + 1
- Y가 짝수면 Y := Y / 2, 홀수면 Y := (Y + 1) / 2
- res + X - Y 를 반환
반복문이 종료되는 시점에는 Y ≤ X가 됩니다. 이때 남은 차이(X − Y)만큼 1 감소 연산을 추가로 수행하면 되므로, 최종 답은 res + X - Y 입니다.
역방향 탐색이 최적인 이유
홀수인 Y를 만들려면 직전에 반드시 1 감소 연산을 한 번 수행했어야 합니다. 따라서 Y가 홀수일 때는 1을 더한 뒤 나누는 것이 유일한 최선의 선택입니다. 또한 짝수일 때 나누기를 미루면 이후에 필요한 감소 연산이 늘어나므로, 가능한 한 빨리 2로 나누는 것이 항상 유리합니다. 이러한 그리디 선택이 전체 최솟값을 보장합니다.
파이썬 구현 예제
다음 구현을 통해 더 잘 이해해 보겠습니다.
class Solution(object):
def brokenCalc(self, X, Y):
res = 0
while Y > X:
res += Y % 2 + 1
Y = Y // 2 if Y % 2 == 0 else (Y + 1) // 2
return res + X - Y
ob = Solution()
print(ob.brokenCalc(5, 8))
입력
5 8
출력
2
정리
이 문제의 핵심은 정방향이 아니라 역방향으로 사고를 전환하는 것입니다. Y를 X 쪽으로 줄여 나가면서 짝수면 나누고 홀수면 1을 더하는 그리디 전략을 적용하면, 시간 복잡도 O(log Y) 안에 최소 연산 횟수를 효율적으로 구할 수 있습니다.