BOJ #1052

---

LEVEL :

Silver1

---

문제 요약 :

같은용량의 물병을 합쳐 k개 이하로 만들어야 할 때 추가로 구매해야 하는 물병의 갯수는?

---

해결 방안 :

모든 물병의 초기 용량이 1이고 두 물병을 합쳐 나간다는 점에서 2의 몫과 나머지를 이용하여야 한다고 생각했고 나머지는 간단한 연산과정을 통해 결과를 도출하는 것이어서 크게 어려움은 없었던 것 같다.

---

시간 복잡도 :

시간복잡도는 while문에서 logN의 연산을 하고, 생성한 arr를 이용해 for문을 돌기 때문에 최대 2logN 즉, O(logN)의 시간복잡도로 문제를 해결가능하다.

---

Solution

import sys
imput = sys.stdin.readline
n,k = map(int,input().strip().split())
arr = []
total_bottle = n
pair_bottle = n
cnt = 1
while pair_bottle != 0 :
    if pair_bottle%2 == 1 :
        arr.append(cnt)
    cnt *= 2
    pair_bottle = pair_bottle//2
    total_bottle = pair_bottle + len(arr)
buy_bottle = 0
for i in range(len(arr)-1) :
    if total_bottle <= k :
        break
    else : 
        buy_bottle += arr[i+1]-arr[i]
        total_bottle -= 1
        arr[i+1] *= 2
print(-1 if total_bottle> k else buy_bottle )