BOJ1052 물병(C++)

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

태그 : 수학, 구현, 그리디, 비트마스킹

사고 흐름

우선 문제에서 정답이 없을 경우 -1 출력이라고 적어놨는데.. 낚시였다. 어려운 조건은 아니라 금방 의심은 들지만 왜 굳이 저런 낚시를 넣었을까 싶다.

아무튼.. 비트마스킹은 굳이 없어도 되고 그냥 2씩 나눠보면서 비트 수가 k개 이하 될 때 까지 2의 배수를 더해주면 된다.

비트 카운팅하는 로직을 짰는데, 세는 라이브러리 함수가 있다는 것 같다.

코드

#include <iostream>
#include <algorithm>
using namespace std;

#define INF 1000000007

int n, k;
int ans;

void solve() {
	while (true) {
		int cnt = 0;
		int i = 0;
		while ((1 << i) <= n) {
			if ((n >> i) & 1) {
				++cnt;
			}
			++i;
		}
		if (cnt <= k) {
			break;
		}

		i = 0;
		while (true) {
			if ((n >> i) & 1) {
				ans += (1 << i);
				n += (1 << i);
				break;
			}
			++i;
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> k;
	solve();
	cout << ans;
}