백준 1052. 물병

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

1052번: 물병

 

이 문제는 처음에 k=1일 경우가 아니면 (2 <= k < n) 무조건 물통을 하나도 사지않고 옮길수 있다고 생각했다.

또한 n이 2의n승이라면 하나의 물병으로 합칠수 있으므로 k가 1이 아니라면 그냥 k보다 큰 2의n승의 숫자가 될때까지 물통을 사면된다고 생각했는데 답이 아니었다.

 

 

#include <iostream>
using namespace std;

int n,k;

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

    // n이 k보다 작으면 그냥 0 출력후 종료
    if(n <= k)
    {
        cout << 0;
        return 0;
    }

    int ans = 0;
    while(true)
    {
        int cnt = 0;
        int temp = n;

        while(temp)
        {
            // 남는 물병이 있음 (합쳐지지 않은 물병)
            if(temp % 2)
                cnt++;

            temp /= 2;
        }

        if(cnt <= k)
            break;

        n++;
        ans++;
    }

    cout << ans;

}