문제

지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번에 K개의 물병을 옮길 수 있다. 하지만, 지민이는 물을 낭비하기는 싫고, 이동을 한 번보다 많이 하기는 싫다. 따라서, 지민이는 물병의 물을 적절히 재분배해서, K개를 넘지 않는 비어있지 않은 물병을 만들려고 한다.

물은 다음과 같이 재분배 한다.

먼저 같은 양의 물이 들어있는 물병 두 개를 고른다. 그 다음에 한 개의 물병에 다른 한 쪽에 있는 물을 모두 붓는다. 이 방법을 필요한 만큼 계속 한다.

이런 제약 때문에, N개로 K개를 넘지않는 비어있지 않은 물병을 만드는 것이 불가능할 수도 있다. 다행히도, 새로운 물병을 살 수 있다. 상점에서 사는 물병은 물이 1리터 들어있다.

예를 들어, N=3이고, K=1일 때를 보면, 물병 3개로 1개를 만드는 것이 불가능하다. 한 병을 또다른 병에 부으면, 2리터가 들어있는 물병 하나와, 1리터가 들어있는 물병 하나가 남는다. 만약 상점에서 한 개의 물병을 산다면, 2리터가 들어있는 물병 두 개를 만들 수 있고, 마지막으로 4리터가 들어있는 물병 한 개를 만들 수 있다.

제한사항

첫째 줄에 N과 K가 주어진다. N은 107보다 작거나 같은 자연수이고, K는 1,000보다 작거나 같은 자연수이다.

접근

문제를 제한사항을 꼼꼼히 살펴보면 풀 수 있는 문제였어요. 물병이 동일한 리터일 경우에 합칠 수 있다고 했는데, 이를 나열해보면,

1 $\to$ [1] : 1개
2 $\to$ [1, 1] : 1개
3 $\to$ [1, 1], [1] : 2개
4 $\to$ [1, 1, 1, 1] : 1개
5 $\to$ [1, 1, 1, 1], [1] : 2개
6 $\to$ [1, 1, 1, 1], [1, 1] : 2개

이를 잘 보면 숫자를 2진법으로 표현해서, 비트 1의 개수가 N으로 구성할 수 있는 물병의 최소 갯수임을 알 수 있어요.

1 $\to$ 1 $\to$ 1
2 $\to$ 10 $\to$ 1
3 $\to$ 11 $\to$ 2
4 $\to$ 100 $\to$ 1
5 $\to$ 101 $\to$ 2
6 $\to$ 110 $\to$ 2
7 $\to$ 111 $\to$ 3
8 $\to$ 1000 $\to$ 1
...

따라서, N의 1 비트 개수가 K보다 작거나 같을 때 조건이 충족하는 것을 알 수 있으며, N을 1씩 증가시키면서 K보다 작거나 같은 조건의 N이 될 경우, 증가시킨 N - 주어진 N을 바로 반환해주시면, 최소 물병을 몇 병사야 하는지 알 수 있게 되요.

답안

#include <iostream>
#include <cmath>

using namespace std;

int getCount(int n) {
    int count = 0;

    while(n > 0) {
        if(n % 2 != 0) ++count;
        n /= 2;
    }
    return count;
}

int main()
{
    int N, K;
    scanf("%d %d", &N, &K);
    if (N <= K)
    {
        printf("0\n");
        return 0;
    }

    int answer = -1;
    for(answer = N; ; ++answer) {
        if(getCount(answer) <= K){
            break;
        }
    }

    printf("%d\n", answer - N);

    return 0;
}