Bin_S+StudyRoom

• 문제

지민이는 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을 출력한다.

• 예제 입력

3 1

13 2

1000000 5

• 예제 출력

1

3

15808

• 접근방식

물통을 사지 않고 최대로 물병을 합쳤을 경우

N=2, {1,1} > {2} > 1병
N=3, {1,1,1} > {2,1} > 2병
N=4, {1,1,1,1} > {2,2} > {4} > 1병
N=5, {1,1,1,1,1} > {2,2,1} > {4,1} > 2병
N=6, {1,1,1,1,1,1} > {2,2,2} > {4,2} > 2병
N=7, {1,1,1,1,1,1,1} > {2,2,2,1} > {4,2,1} > 3병

즉, 물병을 하나도 사지않고 N이 2의 n제곱승일 경우 물병을 1병으로 합칠수 있음, 새로운 물병을 살 수 있으니 물병을 계속 구매할경우 물병의 개수가 결국 2의 n제곱승이 된다. (정답이 없을경우가 없음)

n은 주어진 물병의 개수, cnt는 들고가는 물병, result은 상점에서 구매한 물병의 수
1. 주어진 물병을 최대한 합침 (n을 2로 나누기)
2. 나머지가 발생하면 합쳐지지 않은 물병 존재, cnt++
3. n이 0이 될때까지 1~2반복
4. cnt의 개수가 k 이하일 때 result 출력, 아니면 1~3번 반복

• 코드

#include <iostream>
#include <algorithm>

using namespace std;

int n, k, cnt, result;

int main()
{
    cin >> n >> k;

    // n은 주어진 물병의 개수, cnt는 들고가는 물병, result은 상점에서 구매한 물병의 수
    // 1. 주어진 물병을 최대한 합침 (n을 2로 나누기)
    // 2. 나머지가 발생하면 합쳐지지 않은 물병 존재, cnt++
    // 3. n이 0이 될때까지 1~2반복
    // 4. cnt의 개수가 k 이하일 때 result 출력, 아니면 1~3번 반복
    for (result = 0; ; result++) // 
    {
        int temp = n + result; // 상점에서 산 물병 개수 + 주어진 물병의 개수
        cnt = 0;

        while (temp) // temp != 0
        {
            if (temp % 2 == 1)
            {
                cnt++;
            }
            temp /= 2;
        }

        if (cnt <= k)   break;
    }
    cout << result;
    return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/1052