[백준]1052번 물병 - C/C++

https://www.acmicpc.net/problem/1052

1052번: 물병

문제

지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번에 K개의 물병을 옮길 수 있다. 하지만, 지민이는 물을 낭비하기는 싫고, 이동을 한 번보다 많이 하기는 싫다. 따라서, 지민이는 물병의 물을 적절히 재분배해서, K개를 넘지 않는 비어있지 않은 물병을 만들려고 한다.

물은 다음과 같이 재분배한다.

먼저 같은 양의 물이 들어있는 물병 두 개를 고른다. 그다음에 한 개의 물병에 다른 한쪽에 있는 물을 모두 붓는다. 이 방법을 필요한 만큼 계속한다.

이런 제약 때문에, N개로 K개를 넘지 않는 비어있지 않은 물병을 만드는 것이 불가능할 수도 있다. 다행히도, 새로운 물병을 살 수 있다. 상점에서 사는 물병은 물이 1리터 들어있다.

예를 들어, N=3이고, K=1일 때를 보면, 물병 3개로 1개를 만드는 것이 불가능하다. 한 병을 또 다른 병에 부으면, 2리터가 들어있는 물병 하나와, 1리터가 들어있는 물병 하나가 남는다. 만약 상점에서 한 개의 물병을 산다면, 2리터가 들어있는 물병 두 개를 만들 수 있고, 마지막으로 4리터가 들어있는 물병 한 개를 만들 수 있다.

입력

첫째 줄에 N과 K가 주어진다. N은 107보다 작거나 같은 자연수이고, K는 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 상점에서 사야 하는 물병의 최솟값을 출력한다. 만약 정답이 없을 경우에는 -1을 출력한다.

---

1리터가 든 물병을 더하면 2리터, 2리터가 든 물병을 더하면 4리터가 된다. 이 문제의 핵심은 물병들을 더하면 2의 배수가 된다는 것이다. 2의 배수가 된다면 비트 마스킹 기법을 활용하여 문제를 풀 수 있기 때문이다.

1인 비트가 지금 시점에서 옮겨야 하는 병의 수라고 생각하면 된다. K개보다 1인 비트가 많으면 한 번에 물병을 옮기지 못한다. 그렇다면 상점에서 물병을 하나 더 사 와야 한다. 사 오고 나서 물병을 모두 옮겨 담았을 때 K개 이하의 물병만이 남았다면 성공한 것이다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

using namespace std;
int N, K;
int countBits(int value) {
	int count = 0;
	while (value > 0) {
		if ((value & 1) == 1)
			count++;
		value = value >> 1;
	}
	return count;
}

void solve() {
	for (int i = 0;; i++) {
		if (countBits(N) <= K) {
			cout << i;
			return;
		}
		N++;
	}
}

int main() {
	cin >> N >> K;
	solve();
}

---

비트 마스킹을 SWEA에서 배운 겸 백준에서도 비트 마스킹 문제를 풀어보려 문제를 선정하였다. 처음에는 이게 왜 비트 마스킹 문제이지라는 생각으로 일단 N을 이진수로 바꾸어 보고 빈칸의 개수를 채우려고 하니 정답에 대부분 근접하게 나왔다. 생각을 조금 더 해보니 비트의 하나가 물병이라는 것을 깨달았으며 같은 용량의 물병이 있으면 합치는 데에는 비용이 들지 않으므로 합치는 것이 무조건 효율적이라는 것을 알았다. 그렇게 상점에서 1리터짜리 물병을 더 사 오면서 K개가 되면 되겠다고 생각을 했는데 여기서 무조건 합친기 때문에 K개 이하가 되면 성공이라는 것을 알게 되었다.

비트 마스킹 유형이라는 것을 몰랐다면 꽤나 돌아갔을 것 같은 문제이다. 역시 문제 유형은 여러 가지에 대비되어있는 것이 좋은 것 같다!