[백준][Python] 2885 초콜릿 식사

그리디 / 실버 2

🍫

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

2885번: 초콜릿 식사

 

 

내 풀이

K = int(input())
size = 0 # 구매해야하는 가장 작은 초콜릿의 크기
ans = 0 # 최소 몇 번 쪼개야 하는지
exponent = 0 # 현재 지수
arr = [] # 현재 초콜릿들의 사이즈

while True:
    if pow(2, exponent) >= K:
        size = pow(2, exponent)
        arr.append(size)
        break
    exponent += 1

goal_size = size - K
current_size = goal_size

while current_size > 0:
    for i in arr:
        if current_size >= i:
            current_size -= i
    if current_size == 0:
        break
    current_size = goal_size
    arr.sort(reverse=True)
    min_num = arr.pop()
    arr.append(min_num // 2)
    arr.append(min_num // 2)
    ans += 1

print(size, ans)

 

 

코드 설명

 

상근이는 적어도 K 크기의 초콜릿을 먹어야 한다.

이때 가장 작은 초콜릿을 구매해야 하므로

2의 제곱 값이 K보다 크거나 같아지는 즉시 반복문을 종료한다.

while True:
    if pow(2, exponent) >= K:
        size = pow(2, exponent)
        arr.append(size)
        break
    exponent += 1

 

goal_size: 구매해야 하는 초콜릿(size)의 크기에서 먹어야 하는 초콜릿(K)의 크기를 뺀 값 (남은 초콜릿의 크기)

current_size: goal_size 원본이 변경되는 것을 막기 위한 복사 변수

goal_size = size - K
current_size = goal_size

 

현재 초콜릿들의 사이즈(arr)를 검사하면서, current_size보다 크기가 작은 초콜릿이 있다면 합쳐주고 current_size를 갱신한다.

현재 초콜릿들로 K를 구성할 수 없는 경우, current_size를 다시 goal_size로 돌려놓는다.

arr는 내림차순 정렬하며, 가장 작은 값을 pop 시켜주고 반으로 나눈 값을 두 번 추가해 준다.

ans(최소 몇 번 쪼개야 하는지)를 1 증가시킨다.

while True:
    for i in arr:
        if current_size >= i:
            current_size -= i
    if current_size == 0:
        break
    current_size = goal_size
    arr.sort(reverse=True)
    min_num = arr.pop()
    arr.append(min_num // 2)
    arr.append(min_num // 2)
    ans += 1