백준 1052: 물병 [C++]

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

 

용량 제한은 없고, 처음 상태에는 물 1리터가 들어있는 물병 N개

한번에 옮길 수 있는 물병은 K개

하고자 하는 것: 물을 재분배(같은 양의 물병 2개를 한쪽에 몰아넣음)해, 비어있지 않은 물병이 K개를 넘지 않도록 만들기 (찬 물병이 K개 이하가 되게)

이걸 위해 새 물병(1리터가 들어있음)을 구매할 수 있음

 

ex) N=3, K=1이면

물병 3개, 한번에 1개밖에 옮길 수 없다면

1 1 1

이 상태에서 재분배를 해도

2 0 1 이 되므로 비어있지 않은 물병이 1개 이하가 될 수는 없다.

 

이때 물병 1개를 산다면, 물병이 4개가 되므로

2 0 1 1

이렇게 들어있을거고

2 0 2 0

이래되고

4 0 0 0

최종적으로 이렇게 될 수 있으므로 비어있지 않은 물병이 1개 이하가 될 수 있다.

 

말을 이상하게 해놔서 무슨 소린가 싶었는데 "이동을 한번보다 많이 하기 싫다" 이건 뭔 그냥 쓰잘데기 없는 첨언이었다. 나는 분배를 한번만 한다는 줄... "이 방법을 필요한 만큼 계속한다" 이것만 봐도 된다.

 

여튼 그런 문제고

예시를 보면 감이 오겠지만 각 물병이 담을 수 있는 물의 양은 모두 2의 거듭제곱이다.

즉 N보다 크거나 같은 양의 물을 K개 이하의 물병에 2의 거듭제곱씩만큼 담을 수 있는지를 물어보는 것이다.

현재 물을 담는 데 필요한 물병 개수는 곧 물의 양을 이진수로 표현했을 때의 1의 개수이므로, N에 1씩 추가해가면서 현재 양의 물을 담는 데 필요한 물병 개수를 세고 그 개수가 K보다 작거나 같은지 확인해 최종 답을 출력해주면 된다.

그러니까 비트마스킹 문제다.

 

전체 코드

#include <iostream>

using namespace std;

const int MAX = 26;

//n리터 물을 담는 데 필요한 최소 물병 개수
int bitCount(int n){
    int cnt = 0;
    for(int i=0;i<MAX;i++){
        if (n & (1 << i)){
            cnt++;
        }
    }
    return cnt;
}

//상점에서 사야하는 최소 물병 개수
int minCount(int n, int k){
    int answer = 0;
    while(true){
        if (bitCount(n + answer) <= k){ //k개 이하 물병에 담을 수 있으면
            return answer;
        }
        answer++; //담을 수 없다면 물병추가
    }
}

int main()
{
    int n, k;
    cin >> n >> k;
    cout << minCount(n, k);

    return 0;
}