(Python) - BOJ(1052번) : 물병

https://www.acmicpc.net/problem/1052

1052번: 물병

 

• 해설 :

N개의 물병과 K라는 수가 주어진다. N개의 물병에는 모두 물이 1리터씩 들어있고 같은 양이 들어있는 물병 두 개를 합쳐서 하나의 물병에다 옮길 수 있다. 물병의 개수를 K개로 줄이려고 할 때, 불가능한 경우가 생기지 않게 상점에서 적절하게 물병을 사려고 한다. 이 때, 물병을 사는 최소 개수를 찾는 문제이다. 상점에서 사는 물병엔 물이 1리터씩 들어있다.

 

 

 

 

• 풀이 :

한 번 연산할 때 물병의 개수는 반으로 줄어야 한다. 따라서, 물병을 K개 이하로 만드는 과정에서 물병의 개수가 홀수일 때 물병을 1개씩 사서 합치는 방법이 가장 그리디하다. 반으로 나눈 물병의 개수를 카운트하기 위해 emptyGlass 변수를 사용하였다.  물병을 합칠 때마다 빈 물병이 하나씩 생기므로 빈 물병의 개수가 현재 남은 물병의 개수와 같은 점을 이용하였다.

 

 

 

 

if __name__ == "__main__":
    N,K = map(int,input().split())
    buyCnt = 0
    emptyGlass = 0
    if N <= K:
        print(0)
        exit()
 
    while True:
        buyCnt += 1
        emptyGlass = 0
        tmp = N
        while tmp != 0:
            if tmp%2 != 0:
                emptyGlass += 1
            tmp = tmp//2
        if emptyGlass<=K:
            break
        N+=1
 
    print(buyCnt-1)