[백준 2885] 초콜릿 식사 (python)

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

2885번: 초콜릿 식사

초콜릿 식사 문제

2의 n제곱 개의 정사각형으로 이루어진 초콜릿을 쪼개면서 원하는 개수만큼 먹고 싶을 때, 어느 크기의 초콜릿과 몇 번 쪼개야 가능한지 찾는 문제

while문을 통해 그리디하게 찾아서 해결할 수 있었다.

📌 문제 접근 포인트

1. 초콜릿의 크기를 먼저 정해야한다. 초콜릿의 크기를 정해주기 위해서 초콜릿은 1, 2, 4, 8... 즉 2의 n제곱으로 이루어진 리스트 하나를 K를 커버할 수 있을 만큼 사이즈로 만들어주자. 
2. 리스트에서 K보다 큰 초콜릿들 중 최소가 되어야 하므로 바로 큰 초콜릿을 찾으면 break로 초콜릿을 확정 짓자.
3  이제 초콜릿을 정했으면 쪼개야 한다. 쪼개는 과정에서 초콜릿은 반으로만 쪼갤 수 있다는 점을 생각해야 한다.
입력 예시를 생각하면 K = 6을 원하니까 8칸짜리 초콜릿을 고르고, 8칸짜리를 1번쪼개서 4 + 4로 만들고, 다시 4짜리 한 개를 2+2로 쪼개서 6을 만드는 식으로 만들어야한다. 
그렇다면 K = 5이라면 8칸짜리 초콜릿을 고르고, 8칸짜리를 1번 쪼개 4+4로 만들고, 다시 4짜리 한개를 2+2로 쪼개자. 이때 4+2는 K보다 커지니까 2를 한번 더 쪼개야 한다. 즉 4 + 1 = 5 형태로 만들 수 있게 돼야 한다.
4. K가 0이 될 때까지 위의 3번을 반복해서 쪼갤 수 있도록 구현하면 된다.

⚙️ 내가 푼 정답 코드

import sys
K = int(sys.stdin.readline())
x = [2**i for i in range(21)] # 초콜릿 선택용
for i in x:
    if K <= i: # K 보다 큰 초콜릿을 고르자
        choco = i 
        break
cnt = 0 # 몇번 쪼개야할까?
temp = choco # 쪼개줄 임시의 초콜릿
if K != choco: # 통초콜릿과 사이즈가 다르면
    while K : # 0이 될때 까지 쪼개보자
        temp //= 2 # 쪼갰는데
        if K >= temp: # 원하는 사이즈보다 작으면
            K = K - temp # 그만큼 갉아먹고
            cnt += 1 # 쪼갠 수 증가
        else: # 아니면
            cnt += 1 # 쪼개기만하기
print(choco, cnt)