[c++] 백준 1052 물병

[문제]

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

1052번: 물병

 

[풀이]

2의 거듭제곱은 하나의 물병으로 합칠 수 있는 수이다. 64 = 32+32 = 16+16+16+16 = ... = 1+1+.....+1 이기 때문에 한 병으로 만들 수 있다. 따라서 가능한 최대의 2의 거듭제곱 수를 구한 후 n에서 빼주고 동시에 k도 1씩 감소시켜준다. k가 1이 될 때까지 위의 과정을 반복한 후, k가 1이 되면 남아있는 n이 물병 한 개로 옮길 수 있는 2의 거듭제곱 수가 될 때까지 사야하는 물병 수를 증가시켜 준다. 

예를 들어, 31개의 물병이 있고, 최대 3개까지 한번에 옮길 수 있다고 하자. 31 = 16 + 15이고, 16개의 물병은 2의 거듭제곱수이므로 1병으로 합칠 수 있다. 그럼 문제는 다시 15개의 물병이 있고, 최대 2개까지 한번에 옮길 수 있는 조건으로 변환된다. 다시 15 = 8 + 7이므로 마지막으로 7개의 물병을 1개로 합쳐야 한다. 이를 위해서는 물병 1개를 상점에서 사면 7 + 1 = 8이고, 8은 2의 거듭제곱이므로 하나의 물병으로 합칠 수 있다. 따라서 물병 한 병만 더 사면 된다. 

 

[코드]

// Created by strit on 2022-01-21. boj silver1 1052 물병
#include <iostream>

using namespace::std;
//같은 양의 물이 들어 있는 물병에 대해서 한 개의 물병에 다른 한쪽의 물을 모두 붓는다.
//n개의 물병, k개의 한번에 옮길 수 있는 물병의 개수.
//k개를 넘지 않는 비어 있지 않은 물병을 만든다. 1l 짜리 물병을 살 수 있다.
//첫째 줄에 상점에서 사야하는 물병의 최솟값을 출력한다. 만약 정답이 없을 경우에는 -1을 출력한다.
void renewN(int* n, int* k){
    int maxNum = 1;
    while(maxNum<*n){
        maxNum *= 2;
    }
    maxNum /= 2;
    *n -= maxNum;
    *k -= 1;
}

bool check(int n){ //2의 거듭제곱 판별
    return (n & (n - 1)) == 0;
}

int main() {
    int n, k, bottle = 0;
    cin >> n >> k;

    //1. n보다 작은 최대 2의 제곱으로 만든다.
    //2. k가 1이 될 때까지 1씩 감소시키면서.
    //3. k가 1이되면 그때의 n을 2의 거듭제곱을 만들기 위해 사야하는 물병 개수를 구한다.
    while(k>1){
        renewN(&n, &k);
    }

    while(!check(n)){
        bottle++;
        n += 1;
    }

    cout << bottle;

}