[BOJ] 1052 물병 (Python3)

문제

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

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

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

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

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

입력

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

출력

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

n,k = map(int,input().split())

 3 1

from collections import deque
def solution(n, k):

    remainWater = deque()
    waterLevel = 0
    while n != 1: 
        if n % 2 != 0:
            n = n // 2
            remainWater.append(pow(2, waterLevel))
        else:
            n = n // 2
        waterLevel += 1
    
    remainWater.append(pow(2, waterLevel))
    
    answer = 0

    
    while len(remainWater) > k:
        minWater = remainWater.popleft()
        minWater2 = remainWater.popleft()
        
        if minWater == minWater2:
            remainWater.appendleft(minWater * 2)
        else:
            remainWater.appendleft(minWater2)
            answer += minWater
            remainWater.appendleft(minWater * 2)
            
    print(answer)
    return
            
solution(n, k)

15808

단순구현인줄 알고 구현해서 풀었는데, 알고 보니까 비트마스킹 문제였다.

이걸 정말로 비트마스킹으로 풀었다면 진짜 창의력 대장이 아닐까…?

앞으로 2의 제곱수로 나오는 문제가 있다면, 이진수로 변환하여 비트마스킹으로 간단히 풀리는지 꼭 한번 생각은 해봐야겠다.

아래는 비트 마스킹 풀이, 이렇게 풀면 간단하다. 좀 억지같기도 하지만 차라리 풀이를 알면 코드량이 많지 않은 문제가 베스트인 것 같다.

import sys

n, k = map(int, input().split())

count = 0;

while bin(n).count('1') > k:
    n = n+1
    count = count +1

print(count)