두 개의 숫자 start와 end(start < end)가 주어졌을 때, 다음 두 가지 연산만 사용하여 start를 end로 변환하는 데 필요한 최소 연산 횟수를 구하는 프로그램을 만들어 보겠습니다.
- 숫자를 1 증가시키기
- 숫자를 2배로 곱하기
예를 들어 입력이 start = 5, end = 11이라면 출력은 2가 됩니다. 5에 2를 곱해 10을 만들고, 여기에 1을 더해 11을 만들면 되기 때문입니다.
문제 해결 접근 방법
이 문제는 정방향(start에서 end로)으로 접근하는 것보다 역방향(end에서 start로)으로 거슬러 올라가는 것이 훨씬 효율적입니다. 목표 숫자인 end가 짝수라면 이전 단계에서 2배 연산을 했을 가능성이 높고, 홀수라면 마지막 연산은 반드시 1 증가였을 것이기 때문입니다.
구체적인 알고리즘은 다음과 같습니다.
- 연산 횟수를 저장할 변수 ct를 0으로 초기화합니다.
- end를 2로 나눈 값이 start보다 크거나 같은 동안 반복합니다.
- end가 홀수라면: end에서 1을 빼고(end := end - 1), 2로 나눈 후(end := end / 2), 연산 횟수에 2를 더합니다(ct := ct + 2).
- end가 짝수라면: end를 2로 나누고(end := end / 2), 연산 횟수에 1을 더합니다(ct := ct + 1).
- 반복이 끝나면 남은 차이만큼 더합니다(ct := ct + (end - start)). 이 구간에서는 1 증가 연산만 반복하면 되기 때문입니다.
- ct를 반환합니다.
파이썬 구현 예제
class Solution:
def solve(self, start, end):
ct = 0
while(end / 2 >= start):
if end % 2 == 1:
end -= 1
end = end / 2
ct += 2
else:
end = end / 2
ct += 1
ct += (end - start)
return ct
ob = Solution()
print(ob.solve(5, 11))
입력
5, 11
출력
2
동작 원리 살펴보기
위 예제에서 알고리즘이 어떻게 동작하는지 단계별로 확인해 보겠습니다.
- end = 11은 홀수이므로 1을 빼서 10으로 만들고, 2로 나눠 5가 됩니다. 이때 연산 횟수는 2가 됩니다.
- 이제 end = 5이고 end / 2 = 2.5가 start인 5보다 작으므로 반복이 종료됩니다.
- 마지막으로 ct에 (end - start) = (5 - 5) = 0을 더하면 최종 결과는 2가 됩니다.
이 알고리즘의 시간 복잡도는 O(log end)로, 매 반복마다 end가 절반으로 줄어들기 때문에 매우 효율적입니다. 완전 탐색 방식으로 모든 경우의 수를 확인하는 것보다 훨씬 빠르게 최소 연산 횟수를 구할 수 있습니다.