백준 2885번: 초콜릿 식사 (파이썬

백준 2885번: 초콜릿 식사 (파이썬)

문제 설명

문제 요약

• 상근이가 최소 K개의 정사각형 조각으로 이루어진 초콜릿을 먹으려고 합니다.
• 처음 구매하는 초콜릿은 크기가 항상 \(2^n\) 형태입니다 (1, 2, 4, 8, ...).
• 초콜릿은 정확히 반으로만 쪼갤 수 있습니다.
• 목표: K개 이상의 초콜릿을 얻기 위한 **가장 작은 초콜릿 크기**와 그 초콜릿을 K개로 만들기 위한 **최소 쪼개기 횟수**를 구하는 것입니다.

입력 및 출력

입력	출력
정수 K (1 ≤ K ≤ 1,000,000)	가장 작은 초콜릿 크기, 최소 쪼개기 횟수 (공백으로 구분)

예제

입력: 6

출력: 8 2

---

문제 해결 아이디어

이 문제는 **그리디(Greedy)** 알고리즘과 **이진법**의 원리를 활용하여 풀 수 있습니다.

1. 최소 초콜릿 크기 구하기:
   가장 먼저 해야 할 일은 K개 이상의 조각을 얻을 수 있는 최소 크기의 초콜릿을 찾는 것입니다. 문제 조건에 따라 초콜릿의 크기는 \(2^n\) 형태이므로, K보다 크거나 같은 가장 작은 \(2^n\)을 찾으면 됩니다. 이는 1부터 시작하여 2를 곱해나가며 K보다 커질 때까지 반복하면 됩니다.
2. 최소 쪼개기 횟수 구하기:
   K개의 조각을 얻기 위해 초콜릿을 쪼개는 과정을 시뮬레이션합니다.
   - 가장 큰 초콜릿 조각(처음 구매한 크기)부터 시작합니다.
   - 만약 현재 조각의 크기가 남은 K보다 작다면, 이 조각은 필요한 K개에 포함되지 않는다는 의미입니다. 따라서 이 조각을 반으로 쪼개고 쪼개기 횟수를 1 증가시킵니다.
   - 만약 현재 조각의 크기가 K와 같거나 크다면, 이 조각을 사용하여 K를 만족시킬 수 있다는 의미입니다. 이 경우, 해당 조각을 제외하고 남은 K를 다시 계산합니다. 이 조각을 사용했으므로 더 이상 쪼갤 필요는 없습니다.
   - 이 과정을 K가 0이 될 때까지 반복하며, 쪼갤 때마다 횟수를 셉니다.

예제 분석 (K=6)

• 1단계: 초콜릿 크기
  K=6이므로, 6보다 크거나 같은 최소 \(2^n\)은 \(2^3=8\)입니다.
• 2단계: 쪼개기 횟수
  - 초기 상태: 초콜릿 크기 8, 남은 K=6, 쪼개기 횟수=0
  - 1회차: 현재 조각 크기 8. 6 < 8 이므로 8을 반으로 쪼갭니다 (8 → 4, 4). 쪼개기 횟수 1 증가.
  - 2회차: 현재 조각 크기 4. 6 ≥ 4 이므로 4 조각을 사용합니다. 남은 K는 6-4=2.
  - 3회차: 현재 조각 크기 4. 남은 K=2. 2 < 4 이므로 4를 반으로 쪼갭니다 (4 → 2, 2). 쪼개기 횟수 1 증가.
  - 4회차: 현재 조각 크기 2. 2 ≥ 2 이므로 2 조각을 사용합니다. 남은 K는 2-2=0.
  - K가 0이 되었으므로 쪼개기를 멈춥니다.
  - 총 쪼개기 횟수: 2
• 최종 결과: 8 2

---

전체 코드 (Python)

k = int(input())

choco = 1
while choco < k:
    choco *= 2

current = choco
cnt = 0

while k > 0:
    if k >= current:
        k -= current
    
    current /= 2

    if current > 0 and k > 0:
        cnt += 1

print(f'{choco} {cnt}')

코드 설명

• choco = 1: 초기 초콜릿 크기를 1로 설정합니다.
• while choco < k: choco *= 2: K보다 크거나 같은 최소 2의 제곱수를 찾습니다.
• current = choco: 쪼개기 과정에 사용할 현재 조각 크기를 가장 큰 초콜릿 크기로 초기화합니다.
• while k > 0: 남은 K가 0이 될 때까지 반복합니다.
• if k >= current: k -= current: 현재 조각을 사용합니다. 만약 현재 조각 크기보다 남은 K가 더 크거나 같다면, 현재 조각을 사용하여 K를 줄입니다.
• current /= 2: 다음으로 작은 조각을 확인하기 위해 현재 조각 크기를 반으로 나눕니다.
• if current > 0 and k > 0: cnt += 1: 아직 K를 완전히 채우지 못했고 더 쪼갤 조각이 남아있다면 쪼개기 횟수를 증가시킵니다.
• print(f'{choco} {cnt}'): 최종 초콜릿 크기와 쪼개기 횟수를 출력합니다.

---

결론

이 코드는 초콜릿 식사 문제를 매우 직관적이고 효율적으로 해결합니다. **가장 작은 2의 제곱수**를 찾고, **가장 큰 조각부터 순차적으로 K를 채워나가는 그리디 방식**을 사용하면 최소 쪼개기 횟수를 보장할 수 있습니다. 이는 K의 이진수 표현과도 관련이 깊은데, 각 쪼개기는 2의 거듭제곱 단위로 이뤄지기 때문입니다. 따라서 이진법의 각 자리수를 확인하며 필요한 조각들을 쪼개서 얻는 방식과 동일합니다.