백준 BOJ 1052 - 물병

풀이법이 신기해서 가져와본 문제.

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

1052번: 물병

2의 제곱수 리터 만큼의 물이 들어있는 물병의 갯수가 K개 이하가 되도록

물병을 합쳐보는 문제.

 

처음에는 1리터짜리 물병 a개, 2리터짜리 물병 b개. 4리터짜리 물병 c개....

이렇게 갯수별로 저장해보려고 했었는데

지나치게 뜬구름 잡는 내용인가 싶어서 태그를 까봤다.

 

태그에 "비트마스킹" 이 있는게 좀 결정적이었다고 생각한다.

 

위의 방법대로 갯수대로 저장을 하면,

같은 용량을 가지는 물병이 2개 이상 있다면 반드시 합치는게 이득이기 때문에

각 용량 별로 물병이 1개 또는 0개 있게 되는데,

이를 구현하기 위해서

직접 2로 나눈 몫을 관리하고

2로 나눈 나머지를 남기고 이것저것 해야한다.

 

그런데 놀랍게도 그냥 이진수 간의 덧셈 과정을 생각해보면

2로 나눈 몫이 윗자리로 올라가고

2로 나눈 나머지가 원래 자리에 그대로 남으면서

직접 구현하려고 했던 부분을 상당수 생략할 수 있게 된다.

 

즉, 이 문제는 N+a 인 숫자 M에 대해서,

M을 이진수로 봤을 때 '1' 비트의 개수가 K개 이하가 되도록 하는

최소의 a를 찾는 문제로 변한다.

 

입력의 N이 10^7 = 10000000 이고

N보다 크면서 가장 가까운 2의 제곱수는 2^24 = 16777216이니

1씩 증가시켜가면서 브루트포싱을 해도 정답을 찾을 수 있다.

시간복잡도는 O(NlogN)

 

#include <bits/stdc++.h>
using namespace std;

int count(int k){
	int ans = 0;
	while(k){
		ans += k%2;
		k/=2;
	}
	return ans;
}

int main(){
	int N,K;
	cin >> N >> K;
	
	int ans = 0;
	while(count(N+ans) > K){
		ans++;
	}
	cout << ans;
	return 0;
}