백준 1052 물병

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

같은 크기의 물병을 합쳐서 크기가 2배인 물병을 만든다는 것을 잘 이해하는것이 중요한 문제였다.
위의 내용을 비트로 생각해보면 비트마스킹을 통해 문제를 해결할 수 있겠다라는 생각이 든다.

어떤 수 n 이 있을때 이를 2진수로 나타내면, 비트가 켜진것의 갯수가 물병을 추가하지 않았을 때, 최대한 줄일 수 있는 경우라는 것을 알 수 있다.

제일 처음에는 n에 1씩 더해가며 계산했는데, 그럴 필요가 없이, 비트가 켜진 위치에 1을 더해 해당 비트를 끄고 올림을 만들면 계산량을 확 줄일 수 있다.

n,k = map(int,input().split())
ans = 0
while True:
    count = bin(n).count('1')
    if count > k:
        idx = bin(n)[::-1].index('1')
        ans += 2**idx
        n += 2**idx
    else:
        break
print(ans)