백준 1052번: 물병 - 실버 1

✔ 풀이1 (dict)

딕셔너리 자료형 bottle 사용=> key = 물의 양(liter), value = 물병 개수

다음과 같은 과정을 조건을 만족할 때 까지 반복
👇👇👇👇👇👇👇👇👇👇👇👇
합칠 수 있을 만큼 합치기 -> 가지고 있는 물병의 개수가 K개 이하인지 판별
-> K개 보다 크다면 합치기 위한 필요한 최소 물 구입

import sys
from collections import defaultdict

N, K = map(int, sys.stdin.readline().split())

bottle = defaultdict(int)
bottle[1] = N

liter, buy = 1, 0
while 1:
    while liter in bottle: 
        #해당 liter을 가진 물병이 1병 이상 존재할 때, 합칠 수 있을 만큼 합침
        if bottle[liter] > 1:
            bottle[liter * 2] += bottle[liter] // 2
            bottle[liter] %= 2
        liter *= 2 
        
    if sum(list(bottle.values())) <= K: #총 가지고 있는 물병의 양이 K개 이하일 경우 반복문 종료
        break

    #합칠 수 있는 최소 물병의 수를 구입
    liters = [liter for liter in bottle if bottle[liter] > 0]
    buy += liters[1] - liters[0]
    bottle[liters[0]] = 0
    bottle[liters[1]] = 0
    bottle[liters[1] * 2] += 1
    liter = liters[1] * 2
        
print(buy)

✔ 풀이2 (binary)

만들 수 있는 물의 양 => 1L, 2L, 4L, 8L, 16L ... 2n L
bin(1L * N병) = 물이 각 자리수의 값만큼 존재
=> bin(N)에서 1의 개수 = 총 물병의 개수

총 물병의 개수가 K개 이하가 될 때까지 다음을 반복
👇👇👇👇👇👇👇👇👇👇👇👇
1병 이상 존재하는 최소 물의 양을 찾음 -> 최소 물의 양만큼 물을 구입 -> 물을 합침 (자릿수 올라감)

import sys

N, K = map(int, sys.stdin.readline().split())

buy = 0
while bin(N).count('1') > K:
    idx = bin(N)[::-1].index('1')
    buy += 2**idx  #합치기 위해 필요한 최소 물의 양 구입
    N += 2**idx    #물을 합침
print(buy)