[BOJ] 1052 - 물병 (Python)

 

 

아이디어

 

두 물병을 하나로 합치기 위해서는 두 물병의 물 양이 같아야 한다.

N이 0보다 크거나 같은 범위에서 가장 큰 2의 거듭제곱으로 계속해서 빼나가고,

K 번째 이후에 남은 물을 K 번째 물병에 합치기 위해 필요한 물의 양을 계산한다.

 

 

풀이

 

N에서 뺄 수 있는 가장 큰 2의 거듭제곱 n을 K번 동안 뺀다.

만약 K번 이내에 N이 0이 된다면 물병이 추가로 필요하지 않으므로 0을 출력하고 종료한다.

K 번째 물병까지 모두 채웠다면 마지막 K 번째 물병의 물 양 n에서 남은 물 양 N을 뺀 값을 출력한다.

 

정답은 항상 존재하므로 -1을 출력하는 경우는 없다.

 

N, K = map(int, input().split())
n = 1
while n < N:
    n *= 2
for i in range(K):
    while n > N:
        n //= 2
    N -= n
    if N == 0:
        print(0)
        break
else:
    print(n-N)