[백준 1052] 물병

문제

N개의 물병이 있고 각 물병은 무한대로 물을 담을 수 있다. 이때 최대 K개의 물병만 옮길 수 있다고 하자. 처음에 각 물 병은 1만큼 담겨져있으며 같은 양이 들어있는 두 개의 물병을 하나의 물병으로 합칠 수 있다. 또한 합칠 물병이 없을 때는 1리터의 물병을 사올 수 있다.

이때 최대 K개의 물병으로 만들기위해 사온 물병의 개수를 구하라.

 

입력

첫째 줄에 N과 K가 주어진다. N은 10^7보다 작거나 같은 자연수이고, K는 1,000보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 상점에서 사야하는 물병의 최솟값을 출력한다. 만약 정답이 없을 경우에는 -1을 출력한다.

---

접근

이진수로 접근하는 방법이 있었다.

N이 1부터 8일 때 사오지않고 옮길 수 있는 병의 개수를 구해보면 N을 이진수로 변경했을 때 1의 개수가 된다는 것을 알 수 있다. 만약 1의 개수가 K이하라면 옮길 수 있지만 초과한다면 옮길 수 없다.

 

그렇다면 1의 개수가 K개를 초과할 때는 어떻해야할까?

만약 N=6이고 K=1이라고 하자. 이를 이진수로 표현하면 110이 된다. 이때 1의 개수를 1개로 만들기위해서는 2^1의 자리에 1을 더한다. 즉 6에 2를 더하는 것이다. 그렇다면 1000이되며 물병을 옮길 수 있게된다.

 

구현

- N을 2진수로 변경했을 때 1의 개수를 카운트하여 K개 초과일 때 반복문을 실행한다.

- N을 2진수로 변경하여 처음 1이 나타나는 위치를 찾는다.

- 해당 위치를 P라했을 때 2^P만큼 answer와 N에 더한다.

- answer에 더하는 것은 사온 물병의 개수이고

- N에는 K개 이하로 만들기위해 더하는 것이다.

while bin(N).count('1') > K:
    plus = 2 ** (bin(N)[::-1].index('1'))
    answer += plus
    N += plus

---

 전체 코드

import sys
input = sys.stdin.readline

N, K = map(int, input().split())

answer = 0
while bin(N).count('1') > K:
    plus = 2 ** (bin(N)[::-1].index('1'))
    answer += plus
    N += plus
print(answer)