[BOJ] 1052 물병 C++

문제이해

N개의 물병을 가지고 있는 상태에서 차있는 물병이 K개가 되도록 만드려고 한다. 

재분배는 같은 양의 물이 들어있는 물병 두 개를 고르고 그 다음에 한 개의 물병에 다른 한 쪽에 있는 물을 모두 붓는다.

(상점에서 새로운 1리터 물병을 살 수 있다.)

즉, N으로 같은 양의 물이 들어 있는 물병을 합치면서 K개가 될 수 있는지 확인하고 된다면 상점에서 사야하는 물병의 최솟값을 구해야 하는 문제이다.

 

 

 

아이디어 구상

N, K = 3, 1

1 1 1 -> 2 1 -> 2 2 -> 4로 1개의 물병을 구매하면 된다.

N, K = 13, 2

1 x 13 -> 2x6, 1 -> 4 4 4 1 -> 8 4 1 -> 8 4 4 -> 8 8 -> 16으로 3개의 물병을 구매하면 된다.

위와 같이 N은 2로 나누면서 나머지가 1인 경우 카운트를 해주고 N이 0이 되는 순간 카운트된 값을 K와 비교해서 

K보다 작거나 같은 경우 종료하여 출력하면 된다. 이때 K보다 작거나 같은 경우가 조건인 이유는 n을 2진수로 변환했을 때의 1의 개수가 cnt라고 하면 k보다 큰 cnt는 k개로 나누어질 수 없다는 말과 동일함.

 

 

 

코드

#include <iostream>
#include <algorithm>
using namespace std;
#define fastio cin.tie(0)->sync_with_stdio(0)
int n, k;

int main() {
	fastio;
	cin >> n >> k;

	if (n <= k) cout << "0";
	else {
		int res;
		for (res = 0;; res++) {
			int cnt = 0, tmp = n;
			while (tmp) {
				cnt += tmp % 2;
				tmp /= 2;
			}
			if (cnt <= k) break;
			//결과값이 k보다 큰 경우는 올바른 답이 아니기 때문에 n을 1증가시켜준다.
			n++;
		}
		cout << res;
	}

	return 0;
}