1052] 물병

문제 설명

:  최초 1리터가 담긴 물병들이 N개가 있을때, K개 이하로만 물이 들어있는 병을 만들고자 한다.

이때 같은 양의 물이 담겼을때만 물을 옮길 수 있다. 그렇다면 최소한으로 필요한 물병 구입 개수는?

문제 이해를 예시로 돕자면, N = 8 일때는 1 1 1 1 1 1 1 1 -> 2 2 2 2 -> 4 4 -> 8 로 계속 합칠 수 있으므로 답은 0.

N = 7, K= 1 일때는 1 1 1 1 1 1 1 -> .... -> 4 2 1 로, 1짜리 물병을 하나 더 구입해야 4 2 1 1 -> 4 2 2 -> 4 4 -> 8이 가능해진다.

핵심은 이진법에 있다. N을 이진수로 나타냈을 때, 1의 개수가 물이 들어있는 물병의 개수다.

N=13, K=1인 경우를 말해보자면,  N = 1101(2)이고 8L 짜리 물병, 4L 짜리 물병, 1L 물병으로 나타낼 수 있다는 것이다.

여기에서 1L 짜리 물병을 추가하면? 1110 이 되는 것이고 이것은 8L , 4L, 2L 물병으로 나타낼 수 있다.

여기에 2L 물병을 추가하면 10000 이 되는것이고 16L 물병 하나로 k=1을 만족하게 된다.

즉, 1101 -> 1110 -> 10000 가 되려면 총 1+2 = 3 개의 물병이 필요하고, 이러한 연산은 n & -n 으로 가능하다.
(펜윅트리에서 구간 합을 구할때 사용하는 비트연산 방식과 동일하다)

문제링크 [1052 : 물병]

소스 코드

#include <stdio.h>

int main()
{
	int res = 0;
	int n, k;
	scanf("%d %d", &n, &k);
	while (1) {
		int c = 0;
		for (int i = n; i != 0; i -= (i&-i))c++;
		if (c <= k)break;
		res += n&-n;
		n += n&-n;
	}
	printf("%d\n", res);
	return 0;
}