[LeetCode / Go] 2571. Minimum Operations to Reduce an Integer to 0

문제

LeetCode - The World's Leading Online Programming Learning Platform

You are given a positive integer n, you can do the following operation any number of times:

• Add or subtract a power of 2 from n.

Return the minimum number of operations to make n equal to 0.

A number x is power of 2 if x == 2ⁱ where i >= 0.

---

문제 이해하기

 양의 정수 n이 주어졌을 때, n에 2의 거듭제곱을 더하거나 빼서 0으로 만드는 최소 횟수를 구해야 합니다. 최소한의 횟수로 0을 만들어야 하므로 어떻게 2의 거듭제곱을 더하고 뺄지 최선의 선택(그리디 알고리즘)이 필요합니다. 

 

 첫 번째 예제에서 n은 39로 주어집니다. 2의 거듭제곱과 연관을 지어서 n을 2진수로 표현해 보겠습니다.

2진수로 표현한 39

 39를 2진수로 표현하니 네 개의 1이 들어있는 것을 확인할 수 있습니다. 저 1들을 모두 제거함으로써 n을 0으로 만들 수 있고 이 과정은 2의 거듭제곱을 네 번(1, 2, 4, 32) 빼는 것과 동일합니다. 그런데 이렇게 단순히 빼기만 하는 것은 최선의 선택이 아닙니다.

 

 39의 최하위 비트부터 세 개의 1이 연속으로 나열되어 있는 것을 보실 수 있습니다. 우리는 2의 거듭제곱을 빼는 것 뿐만 아니라 더할 수도 있으며, 이를 통해 두 개 이상의 연속된 1을 하나의 1로 압축할 수 있습니다.

39에 1을 더한 결과

 보시는 바와 같이 39에 2⁰=1을 더하니 네 개 였던 1의 개수가 두 개로 줄어든 것을 확인할 수 있습니다. 연속된 1의 개수가 m개일 경우, 한 번의 더하기로 m-1개의 1을 제거할 수 있으므로 총 m-2번의 빼기 연산을 제거하는 효과를 볼 수 있습니다. 이렇게 2의 거듭제곱을 더하여 두 개 이상의 연속된 1을 하나의 1로 압축하고, 더 이상 압축할 것이 남아있지 않을 때 남은 1들을 제거해주는 식으로 최적해를 구할 수 있습니다.

---

코드

func minOperations(n int) int {
	k := 1
	cnt := 0

	for i := 0; k < n; i++ {
		if k&n > 0 {
			if k<<1&n > 0 {
				n += k
				cnt += 1
			}
		}
		k = k << 1
	}

	for n > 0 {
		cnt += n & 1
		n >>= 1
	}

	return cnt
}

시간: 1ms

메모리: 1.86MB

분류: 그리디 알고리즘, 비트 연산

 

글에서 수정이 필요한 부분이나 설명이 부족한 부분이 있다면 댓글로 남겨주세요!