백준 1052번 물병

#include<iostream>
 
#define endl "\n"
using namespace std;
 
int N, K, Answer;

 
int Add_Water(int x) {
    int Cnt = 0;
    while (x > 0) {
        if (x % 2 == 1) {
        	Cnt++;
        }
        x = x / 2;
    }
    return Cnt;
}

 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N >> K;	
     if (N <= K) {
     	cout << 0 << endl;
     } else {
        while (1) {
            int Temp_Result = Add_Water(N);
            if (Temp_Result <= K) {
            	break;
 			}
            Answer++;
            N++;
        }
        cout << Answer << endl;
    }
    return 0;
}

비트마스크가 이번주 주제라 비트마스크 위주로 생각해봤는데 정말 모르겠어서 다른 방법으로 풀었다. 일일히 손으로 시뮬레이션 한 결과 N이 2의 제곱승일 경우 물병 한병으로 합칠 수 있다는것을 알아내었고 문제 조건 중 물병을 사올 수 있다고 하였으니 물병을 못합쳐서 못들고가는 일은 없다는 것이다. ( 다만 사온 물병 카운트가 k이상일 경우는 실패의 경우로 해당된다.)

while문 안에서 계속 2로 나누어 주며 그 나머지가 1일 경우엔 합쳐지지 못한 물병이 있다는 뜻이므로 cnt를 증가시켜준다
-> 이 갯수만큼 나중에 물병을 새로 산다고 생각하면된다.