[1052번 물병]-C++ (비트마스킹)

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

https://velog.io/@statco19/boj-1052
한 번 풀었던 문제에 대한 다른 풀이로 작성해보려고 한다. 비트마스킹으로도 해결 가능한 문제였다.

비트마스킹,, 이름만 들어도 어려워 보이는 자료구조이다. https://latte-is-horse.tistory.com/364 블로그의 풀이를 참고했다.

풀이

예시를 들어 설명하는 것이 이해가 더 빠를 것 같다. 문제 입력 예시 2번을 보면 13리터를 2개의 물병으로 들고 가려고 한다. 1리터짜리 13개의 물병의 경우, 최대한 합쳐 나가다보면 {8,4,1}로 합쳐져 3개의 물병이 남게 된다.
여기서 눈치를 챘다면 정말 뛰어난 실력의 소유자라고 할 수 있다. 남은 물병의 용량이 항상 2의 제곱수로 만들어지기 때문에, 처음에 주어진 N의 값을 2진수로 나타내었을 때 1의 개수가 최대한 합쳤을 때 남게 되는 물병의 개수와 같아진다!!

13의 경우 2진수로 표현하면 1101이 된다. 따라서 항상 물의 양이 2배씩 늘어나며 합쳐지는 특성을 생각했을 때 최대한 물병을 합쳤을 때 8리터 1병, 4리터 1병, 1리터 1병이 남게 되는데 그게 바로 2진수 표현과 같아진다.

이제 주어진 N을 최대한 합쳤을 때 몇 병이 남게 되는지 알게 되었다. 그럼 우리는 이제 K병 아래로 만들고 싶다. 2^0의 해당하는 가장 오른쪽부터 1이 등장할 때마다 그 자리에 1을 더해서 0으로 만들어 주려고 한다. 최종 목표는 주어진 N보다 크면서 가장 작은 2의 제곱수를 만드는 것이다(즉, 1<<(ceil(log2(N)))의 값을 만드려고 한다).

오른쪽부터 1이 등장할 때마다 해당 자리에 1을 더해주고 나온 결과에서 1의 개수를 센다. 1의 개수가 K개보다 작다면 while loop에서 빠져나온다. 그렇게 계속 반복하여 도중에 while loop을 빠져나오지 못할 경우, N보다 크면서 가장 작은 2의 제곱수까지 가서 while loop을 빠져 나오게 된다.

C++ 코드

#include <bits/stdc++.h>

#define ll long long
#define sf scanf
#define pf printf
using namespace std;
typedef pair<int,int> pint;
typedef vector<int> vint;
const int INF = 0x3f3f3f3f; const int mINF = 0xc0c0c0c0;
const ll LINF = 0x3f3f3f3f3f3f3f3f; const ll mLINF = 0xc0c0c0c0c0c0c0c0;

int ans;
int N,K;
bitset<32> bs;

void sol() {
	bs = N;
	int cnt;
	int idx;
	while(1) {
		idx = -1;
		cnt = 0;
		int tmp = N;

		int i = 0;
		while(tmp) {
			if(tmp&1) {
				if(idx == -1) idx = i;
				cnt++;
			}
			tmp >>= 1;
			i++;
		}
		
		if(cnt <= K) break;
		else {
			bs = N = N + (1<<idx);
			ans += 1<<idx;
		}
	}

	return;
}

int main() {
	// ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	sf("%d %d", &N, &K);
	
	sol();
	
	pf("%d\n", ans);

	return 0;
}

실행결과