1052(물병) - 해결

물병

 

문제

지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번에 K개의 물병을 옮길 수 있다. 하지만, 지민이는 물을 낭비하기는 싫고, 이동을 한 번보다 많이 하기는 싫다. 따라서, 지민이는 물병의 물을 적절히 재분배해서, K개를 넘지 않는 비어있지 않은 물병을 만들려고 한다.

물은 다음과 같이 재분배 한다.

 

먼저 같은 양의 물이 들어있는 물병 두 개를 고른다. 그 다음에 한 개의 물병에 다른 한 쪽에 있는 물을 모두 붓는다. 이 방법을 필요한 만큼 계속 한다.

 

이런 제약 때문에, N개로 K개를 넘지않는 비어있지 않은 물병을 만드는 것이 불가능할 수도 있다. 다행히도, 새로운 물병을 살 수 있다. 상점에서 사는 물병은 물이 1리터 들어있다.

예를 들어, N=3이고, K=1일 때를 보면, 물병 3개로 1개를 만드는 것이 불가능하다. 한 병을 또다른 병에 부으면, 2리터가 들어있는 물병 하나와, 1리터가 들어있는 물병 하나가 남는다. 만약 상점에서 한 개의 물병을 산다면, 2리터가 들어있는 물병 두 개를 만들 수 있고, 마지막으로 4리터가 들어있는 물병 한 개를 만들 수 있다.

 

입력

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

 

출력

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

---

처음에는 생각이 안났다가 가장 먼저 생각난 것이 2의 배수면 1개로 줄일 수 있다는 것.

그렇게 생각하니 생각난 것이 이진수 변환. 이진수 변환을 하면 최대한 줄일 수 있는 만큼 물병을 줄인 모양을 나타낸다고 생각하게 되었다. 그래서 1의 갯수가 최대한 물병 갯수를 줄였을 때의 물병 수가 되기 때문에 이를 이용하였다.

K보다 작을 때 까지 구하고 아니라면 N에 1씩 더해서 반복을 해주었다.

여기서 내가 잘못생각한 부분이 있는데 N이 10,000,000을 넘으면 안된다고 생각을 해버렸다. 처음 N이 그런거고 더하면서 그 수가 넘을 수 있는데 착각을 하였다. 결국 이 문제에서 -1이 나오는 경우는 없게 된다.

계속해서 물병을 더하면 언젠가 2의 배수가 될 수 있기 때문에 -1이 되는 경우는 없다. 

만약 내가 문제를 냈다면 물의 양 자체가 10,000,000을 넘을 수 없다고 문제를 냈을 것 같다. 그렇게하면 (8388608 2)와 같은 경우는 -1이 나올 것이기 때문이다.

 

import sys
#N K
N, K = map(int,sys.stdin.readline().split())

# 물병넣는 수
count = 0
# 물의 양에 대한 제한이 없어서 결국 -1이 나오는 경우가 없음.
# 그래서 K보다 작아질때 까지 반복
while 1:
    # 이진수로 바꾸면 최대한 물병을 줄일 수 있는 모양으로 출력이 되고 
    # 1이 물이 있는 물병의 역할을 한다. 그 수가 K보다 적을 때 까지
    if bin(N).count('1') <= K:
        break
    # 조건을 만족하지 못하면 
    # 물병을 하나씩 추가
    # 이부분을 줄이려면 줄일 수 있을 듯.
    N += 1
    count += 1

print(count)