문제 설명
지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번에 K개의 물병을 옮길 수 있다. 하지만, 지민이는 물을 낭비하기는 싫고, 이동을 한 번보다 많이 하기는 싫다. 따라서, 지민이는 물병의 물을 적절히 재분배해서, K개를 넘지 않는 비어있지 않은 물병을 만들려고 한다.
물은 다음과 같이 재분배 한다.
먼저 같은 양의 물이 들어있는 물병 두 개를 고른다. 그 다음에 한 개의 물병에 다른 한 쪽에 있는 물을 모두 붓는다. 이 방법을 필요한 만큼 계속 한다.
이런 제약 때문에, N개로 K개를 넘지않는 비어있지 않은 물병을 만드는 것이 불가능할 수도 있다. 다행히도, 새로운 물병을 살 수 있다. 상점에서 사는 물병은 물이 1리터 들어있다.
예를 들어, N=3이고, K=1일 때를 보면, 물병 3개로 1개를 만드는 것이 불가능하다. 한 병을 또다른 병에 부으면, 2리터가 들어있는 물병 하나와, 1리터가 들어있는 물병 하나가 남는다. 만약 상점에서 한 개의 물병을 산다면, 2리터가 들어있는 물병 두 개를 만들 수 있고, 마지막으로 4리터가 들어있는 물병 한 개를 만들 수 있다.
제한 사항
풀이
문제를 요약하면, N개의 물병을 적절히 합쳐 K개 이하로 만드는 방법을 찾는 것이다.
이때, 제한 없이 새로운 물병(1)을 살 수 있으며 이를 최소화하는 것이 목표이다.
처음에는 물병을 합치는 것에 집중했다.
한 번 합치면 물병은 절반으로 줄어들고 만약 홀수라면 1개가 추가된다.
이를 반복하다 보면 결국 이진수와 같이 표현이 될 것이라 생각했다.
그럼 x개를 더했을 때 물병을 k개 이하로 합칠 수 있는지 판단할 수 있다.
n+x를 이진수로 표현한 뒤 1의 개수를 세면 된다.
x를 찾기 위해 이진 탐색을 진행하려 했지만 불가능하다고 범위를 올리거나 가능해서 범위를 내리는 등의 논리가 맞지 않았다.
N, M이 충분히 작기 때문에 n이 0일 때부터 하나씩 테스트해 보면 된다.
즉, 그리디로 접근하는 것이다.
이진수를 표현하는 것을 직접 구현해도 좋겠지만 간단하게 bitset을 이용하여 해결할 수 있다.
전체 코드
#include <bits/stdc++.h>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9
using namespace std;
int main()
{
INPUT_OPTIMIZE;
int n, k;
cin >> n >> k;
if (k >= n)
{
cout << 0;
}
else
{
int answer = 0;
while (1)
{
bitset<30> num(n);
if (num.count() <= k) break;
n++;
answer++;
}
cout << answer;
}
return 0;
}