[백준/Python] 1052번 - 물병

문제

1052번 - 물병

해결 과정

• 이진수로 접근하라
• 물병의 갯수를 이진수로 변환했을 때 1의 갯수가 물을 최대로 합친 후의 물병의 갯수이다. 해당 값이 k보다 작을 때까지 물병을 하나씩 추가한다.
• 1개씩 추가하면서 코드를 구현해도 되지만 속도가 느리다.
• 이진수값으로 추가하면서 코드를 구현

시행착오

• 수학적으로 접근해보기 위해 노력했으나.. 실패
• 물병의 양이 이진수일 때 1병인 것을 알았음
• 힌트 획득: 이진수로 접근 bin()

풀이

import sys
n, k = map(int,sys.stdin.readline().split())

bottle = 0
while bin(n).count('1') > k:
  x = 2 ** (bin(n)[::-1].index('1'))
  bottle += x
  n += x
  
print(bottle)