[python] 백준 2885번 : 초콜릿 식사

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

2885번: 초콜릿 식사

 

다음과 같이 k 값으로 6이 주어진 경우, 상근이가 구매해야하는 가장 작은 초콜릿의 사이즈는 2의 제곱수인 8이어야 하고 사이즈가 D일 경우, D/2으로만 자를 수 있다고 했기에 2번을 자르면 상근이가 원하는 초콜릿 6개를 만들 수 있다.  

해당 알고리즘을 구현하자면 아래와 같다. 

 

import sys
input = sys.stdin.readline
# 초콜릿 먹는 개수
k = int(input())
# 1,2,4,8,16 .. 초콜릿 크기(정사각형의 개수)를 정하기 위한 변수
size = 1
# 잘라야 하는 횟수 카운트
count = 0
while size < k:
    size = size << 1
    
result1 = size

while k > 0:
    if k >= size:
        k -= size
    else:
        size //= 2
        count += 1

print(result1, count)

상근이가 18개의 정사각형을 가지는 초콜릿을 원하는 경우, 최소한의 크기의 초콜릿을 요구하므로 크기가 32인 초콜릿을 골라야한다. 이처럼 k라는 원소가 주어진 경우, k보다 크면서 가장 작은 2의 제곱수를 구하는 것으로 초콜릿의 사이즈를 구할 수 있다. 이 아이디어는 첫번째 while문을 통해 구현되었다.  

 

그리고 나서 우리는 k 크기의 초콜릿을 상근이가 먹을 수 있도록 잘라주어야 한다. 이는 2번째 while문 동작을 통해 해결할 수 있다.

크기가 18인 초콜릿은 구하기 위해 32를 반으로 자르면 초콜릿의 사이즈는 16, 16이 된다. 이때 자르는 횟수 count 값이 1 증가한다. 그리고 나서 16크기의 사이즈의 초콜릿은 상근이가 갖게 되었기에 k = 18에서 16을 빼준다. 이제 사이즈가 2인 초콜릿을 구해주기 위해서 반쪽은 상근이를 주고 남아있는 16 사이즈의 초콜릿을 잘라야 한다. 그러면 8,8이 되고 그 다음번에는 4,4 그 다음번에는 2,2 .. 이렇게 나머지 3번의 카운트값이 증가하고 나서 상근이는 사이즈 2의 초콜릿을 얻게 된다.