[백준][그리디][비트마스킹] 1052.물병

1052.물병

1052번: 물병

 

• 풀이
  • N의 이진수 값의 1의 개수는 물병 수
    • 물병 수가 k개 이하이면 더 구매할 필요 없음
  • 2^i 값은 물병의 리터값이 된다
  • 구매해야 하는 물병 양 
    • 보수 개념 이용
    • ex) 13,1
      • 1101(2) -> 왼쪽에서부터 보면서 1개가 구해지면 그위치 값 1000(2) - 101(2)  

 

#같은 양의 물 -> 합칠 수 있음
#상점에서 1L 물병 구매가능
#비어있지 않은 K개이하의 물병을 만들기위해 구매해야할 물병 최소개수
n,k=map(int,input().split())
bottle=0
result=-1

lst=list(reversed(format(n,'b').rstrip()))
if lst.count('1')<=k:
    result=0
else:
    for i in range(len(lst)-1,-1,-1):
        if lst[i]=='1':
            bottle +=1
        if bottle==k:
            result=2**i - sum([2**int(j) for j in range(0,i) if lst[j]=='1'])
            break

print(result)