[solved.ac 실버1] 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의 13, 2가 입력된 상황을 생각해보자.

물통 하나당 1리터가 들어있으니까 나열해보면 1이 13개 있는 모양이다.

이제 같은 양끼리 합쳐서 개수를 줄일 수 있으니까 1씩 모두 묶어서 2로 만들고

만들어진 2를 모두 묶어서 4로 만들고, 

4를 묶어서 8을 만들면

3개의 물통이 남고, 각각 8, 4, 1리터가 들어있다.

 

개수를 줄이기 위해서는 1리터짜리 물통을 몇 개 사서 다시 합치는 과정이 필요하다.

일단 하나를 사보면 개수는 줄어들지 않았지만 1리터 짜리 물통을 2리터로 만들 수 있다.

현재 8, 4, 2 만큼이 있는 것이다.

 

여기에 물통 2개를 추가로 구입해보면 다음과 같다.

새로 산 물통 2개로 2리터를 만들고, 순차적으로 4리터, 8리터, 16리터로 합칠 수 있게 되면서 3개였던 물통을 1개로 만들 수 있게 되었다.

지민이는 최대 2개까지 옮길 수 있기 때문에 옮길 수 있는 상태가 된 것이다.

---

이것을 이진수로 표현해보면 다음과 같다.

2진수로 바꿔보면 1의 개수가 물통의 개수라는 것을 알 수 있다.

그래서 목표는 1의 개수를 줄이는 것이 되고, 1의 개수를 줄이기 위해서는 1이 있는 자리에 1을 더해서 0으로 만드는 과정이 필요하다. 그렇게 하면 최소한 1의 개수가 더 늘어나지는 않는다. 0이 있는 자리에 1을 더하면 1의 개수가 늘어날 것이다.

이때 1을 왼쪽부터 더하는 것이 아니라 가장 오른쪽에 있는 1에 더해야 한다. 왜냐하면 이진수로 표현한 숫자에서 가장 오른쪽에 있는 숫자가 더 작은 숫자이기 때문에 1101 라는 이진수가 있는 경우 맨 앞에 1을 더한 경우는 8만큼을 더한 것이고, 맨 오른쪽에 1을 더한 경우는 1만큼을 더한 것이기 때문이다.

 

파이썬에서는 bin() 함수를 통해 10진수를 2진수로 바꿀 수 있다(문자열로 바뀐다). 그리고 index() 함수를 사용해서 특정 문자의 위치를 알 수 있는데 왼쪽에서부터 찾기 때문에 bin() 함수로 이진수 문자열을 만든 후 역순으로 뒤집어 index() 함수로 '1'의 위치를 찾아서 해당 위치에 숫자를 더해주면 된다.

전체 코드

n, k = map(int, input().split())
answer = 0
while bin(n).count('1') > k:
    idx = bin(n)[::-1].index('1') # 1이 오른쪽에서 몇 번째에 있는지 찾기
    answer += 2 ** idx # 2 ^ (idx) 만큼 더하기
    n += 2 ** idx # 2 ^ (idx) 만큼 더하기
print(answer)

채점 결과