백준 1052번 파이썬 풀이 : 물병

문제 링크 : https://www.acmicpc.net/problem/1052

1052번: 물병

문제

지민이는 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을 출력한다.

 

# 문제 풀이 ( 실버 1 ) (그리디 알고리즘, 시뮬레이션, 비트마스킹)

def check(num):
    answer = 0
    while True:
        a = num // 2
        b = num % 2
        answer += b
        num = a
        if num == 0:
            break
    return answer

check 함수는 최대로 합칠 수 있는 개수를 반환하는 함수이다. 

num이라는 물병의 개수를 입력 받는다. num을 2로 나누었을 때 몫은 물병의 수가 되고 나머지는 묶이지 않은 수가 된다. 따라서 answer에 묶이지 않은 수를 더해주면 추가로 구매해야 하는 물병의 개수가 나오게 된다.

몫이 0이 되면 더이상 합칠 물병이 없기 때문에 반복문을 멈춰주고 answer를 리턴한다.

 

n, k = map(int, input().split())
if k >= n:
    print(0)
else:
    i = n
    while True:
        if check(i) <= k:
            print(i-n)
            break
        else:
            i += 1
 

k가 n보다 크거나 같게 되면 합칠 필요가 없기 때문에 0을 출력해준다. (예외처리)

i 는 n에서 시작해서 1씩 증가하며 check(i) 가 k 이하가 되는 첫번째 수를 찾는다.

그 수가 최소로 더 사야할 물병의 수가 된다.

 

문제를 위와 같이 해결하는 방법도 있지만 이 문제에서 알고리즘 분류를 살펴보면 비트 마스킹이라고 되어있다.

 

# 비트 마스킹이란?

용어 그대로 bit 에 관한 것이다. 비트는 이진 숫자를 뜻하는 말로 컴퓨터에서 사용되는 데이터의 최소 단위이다.

 

따라서 이번 문제는 위 풀이 처럼 반복문과 사칙연산을 사용하여 푸는 것이 아닌 비트(2진수)를 사용하여 풀어야 올바른 풀이라고 생각되어 검색하던 중 좋은 풀이를 발견하게 되었다.

 

# 문제 풀이 (2진수)

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)

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