문제 개요
두 개의 값 start(시작 값)와 end(목표 값)가 주어졌을 때, 아래 두 가지 연산만 사용하여 start를 end로 변환하는 데 필요한 최소 연산 횟수를 구하는 프로그램을 작성해 보겠습니다.
- 값을 1 감소시키기
- 값을 2배로 만들기
예를 들어 start = 2, end = 7이라고 가정해 봅시다. 이때 정답은 3입니다. 2에 2를 곱해 4를 만들고, 다시 2를 곱해 8을 만든 뒤, 마지막으로 1을 빼서 7에 도달할 수 있기 때문입니다.
접근 방법: 역방향 추적
이 문제는 start에서 end로 순방향으로 접근하는 것보다, end에서 start로 거꾸로 거슬러 올라가는 방식으로 풀면 훨씬 효율적입니다. 핵심 로직은 다음과 같습니다.
- end ≤ start인 경우: 더 이상 나누거나 곱할 필요 없이, 남은 차이만큼 1씩 조정하면 됩니다. 따라서
ans + (start - end)를 반환합니다. - end가 홀수인 경우: 2를 곱한 결과는 항상 짝수이므로, 홀수 상태의 end에 도달한 마지막 연산은 반드시 "1 감소"였습니다. 역방향으로 이를 되돌리려면 end에 1을 더하고 연산 횟수를 1 증가시킵니다.
- end가 짝수인 경우: 마지막 연산이 "2 곱하기"였을 가능성이 있으므로, end를 2로 나누고 연산 횟수를 1 증가시킵니다.
이 방식은 매 단계마다 end를 절반 이하로 줄이므로 시간 복잡도는 O(log end)로 매우 효율적입니다.
구현 코드
class Solution:
def solve(self, start, end):
ans = 0
while True:
if end <= start:
return ans + start - end
elif end % 2:
end += 1
ans += 1
else:
end //= 2
ans += 1
ob1 = Solution()
start = 2
end = 7
print(ob1.solve(start, end))
입력
2, 7
출력
3
동작 과정 살펴보기
- end = 7은 홀수이므로 8로 만들고, ans = 1
- end = 8은 짝수이므로 4로 나누고, ans = 2
- end = 4는 짝수이므로 2로 나누고, ans = 3
- 이제 end(2) ≤ start(2)이므로 ans + (start - end) = 3 + 0 = 3 반환
이처럼 역방향 그리디 기법을 활용하면 불필요한 탐색 없이 로그 시간 안에 정답을 구할 수 있습니다.