BAEKJOON 1052 - 물병

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

완전 탐색으로 시도를 할 경우 시간 제한안에 풀 수 없기 때문에 다른 방법을 찾아봐야 됩니다.

n, k 가 19, 1 일 경우

19를 2진수로 표현할 경우 10011 이 됩니다. 이 중 16의 경우 하나의 물병으로 옮겨 담을 수 있고 2와 1이 남게 됩니다. 여기서 1을 더하게 되면 4가 남게 되고 4에 4와 8을 더하게 되면 정답이 됩니다.

만약 k가 2일 경우 1만 더하게 되면 16과 4가 남기 때문에 정답이 됩니다.

이와 같이 n을 2진수로 표현한 후 bit count 가 k 보다 같거나 작아질 때 까지 물을 더하면 답을 구할 수 있습니다.

#include <fstream>
#include <iostream>
#include <cstring>
#include <climits>
#include <algorithm>
 
#include <vector>
using namespace std;
 
vector<int> convertBase10ToBase2(int num, int& bitCount)
{
    vector<int> ret(100, 0);
    int temp;
    bitCount = 0;
    int i = 0;
    do 
    {
        temp = num % 2;
        if (temp == 1)
            bitCount++;
        ret[i] = temp;
        num /= 2;
        i++;
    } while (num > 0);
    return ret;
}
 
int main()
{
    int n, k;
    cin >> n >> k;
    int bitCount = 0;
    vector<int> base2 = convertBase10ToBase2(n, bitCount);
 
    int ret = 0;
    int i = 0;
    while (bitCount > k)
    {
        if (base2[i] == 1)
        {
            ret += pow(2, i);
            base2[i] = 0;
            bitCount--;
            for (int j = i + 1; ; j++)
            {
                if (base2[j] == 1)
                {
                    base2[j] = 0;
                    bitCount--;
                }
                else
                {
                    base2[j] = 1;
                    bitCount++;
                    break;
                }
            }
        }
        i++;
    }
 
    cout << ret << endl;
    return 0;
}