[::-1]
: 역순으로 돌린다
bin()
: 이진수로 표현
N개의 물병
K개 > 채워진 물병.
이때 같은 양의 물이 들어있는 물병 2개만 합칠 수 있다.
상점에서 추가로 사야하는 물병의 최솟값을 구해라.
ex) N = 3, K = 1 일 때, 물병 3개로 1개 이상의 물병을 만들어라.
2의 제곱이어야 K개의 물병으로 옮길 수 있습니다. 즉 이진수로 문제를 접근해야합니다.
bin(3) == 0b11
bin(3)[::-1] == 11b0
bin(n)[::-1].index('1') == 0
'1'이 나오는 첫번째 index는 0.
bin(n).count('1')
: '1'의 개수를 셈. 즉 이진수로 몇개의 물병이 만들어질 수 있는 지를 확인할 수 있음.
ex) 3 -> 0b11 -> 2^1리터 물병, 2^0리터 물병이 만들어짐을 확인할 수 있음.
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
cnt = 0
print((bin(n)[::-1].index('1')))
while bin(n).count('1') > k:
a = 2 ** (bin(n)[::-1].index('1'))
# 가장 말단의 이진수를 0으로 만들어주기 위해서
cnt += a
n += a
print(cnt)