1. 문제 설명

물병

2. 문제 분석

n은 1리터 짜리 물병 n개다. 같은 양일 때 합쳐 빈 병을 만들 수 있으므로, 2의 거듭제곱의 합으로 n을 가장 적은 수의 물병을 써서 표현할 수 있다. k보다 현재 물병 수가 많다면 물이 가장 적게 든 물병 두 개를 꺼내서 상점에서 물병을 사들여 빈 병을 만들자.

• 그리디 알고리즘 유형으로 나와 있는 문제인데, 특성 상 2의 거듭제곱의 합으로 처음에 주어진 n을 매우 빠른 속도로 줄일 수 있어 76ms만에 문제를 해결할 수 있었다.

3. 나의 풀이

import math
import heapq

n, k = map(int, input().split())
# n은 [1, 1, 1, 1... 1]로 표시할 수 있다. 각 1+1 -> 2, 2+2 -> 4 등 2의 거듭제곱의 합으로 n을 표시한다.

purchased = 0
bottles = []

while n !=0:
    exp = 0
    while n - 2**exp >=0: exp += 1
    exp -= 1

    heapq.heappush(bottles, 2**exp)
    n -= 2**exp

while len(bottles) > k:
    bottle1 = heapq.heappop(bottles)
    bottle2 = heapq.heappop(bottles)
    # 가장 적은 수의 병을 구매해서 빈 병을 만들자.
    # 가장 적게 채워진 두 개의 물병을 bottles 힙에서 뽑는다.
    purchased += bottle2 - bottle1
    # bottle1에 bottle2보다 부족한 양을 채워서 합치면 빈 병 하나가 만들어진다.
    heapq.heappush(bottles, bottle2*2)
    # bottle1과 bottle2를 합쳐서 만들어진 병에 담긴 물의 양은 bottle2*2.

print(purchased)