백준 2885번: 초콜릿 식사 (C++)

백준 2885번: 초콜릿 식사 (C++)

문제

백준 2885번 "초콜릿 식사" 문제는 상근이가 점심으로 초콜릿을 먹기 위해 필요한 최소한의 초콜릿 크기와 쪼개기 횟수를 구하는 문제입니다. 문제의 주요 내용은 다음과 같습니다:

• 초콜릿은 막대 모양이며, 정사각형 N개로 이루어져 있습니다. N은 항상 2의 제곱수(1, 2, 4, 8, 16, ...)입니다.
• 상근이는 최소 K개의 정사각형을 먹어야 하며, 초콜릿을 쪼개서 정확히 K개를 만들고 나머지는 선영이에게 줍니다.
• 초콜릿은 반으로만 쪼갤 수 있습니다(즉, 크기 D인 초콜릿은 D/2 + D/2로 나뉨).
• 입력: K (1 ≤ K ≤ 1,000,000)
• 출력: 구매해야 하는 가장 작은 초콜릿 크기와 최소 쪼개기 횟수

예제

• 입력: 6
• 출력: 8 2

---

아이디어

이 문제를 해결하기 위해 다음과 같은 접근법을 사용하였습니다:

1. 초콜릿 크기 계산:
   - K 이상인 가장 작은 2의 제곱수를 찾습니다. 이는 K ≤ 2^n을 만족하는 최소 n을 구하여 2^n으로 계산합니다.
   - 예: K=6일 때, \(2^2=4 < 6\), \(2^3=8 \geq 6\)이므로 초콜릿 크기는 8입니다.
2. 쪼개기 횟수 계산:
   - 초콜릿을 반으로 쪼개며 K개의 정사각형을 만듭니다.
   - 분기점:
   • K ≥ 현재 조각 크기: 해당 조각을 사용하고 K에서 조각 크기를 뺍니다.
   • K < 현재 조각 크기: 조각을 반으로 쪼개고 다음 크기로 넘어갑니다.
   • K = 0: 더 이상 쪼갤 필요가 없으므로 종료합니다.
   - 쪼개기 횟수는 조각을 쪼갤 때마다 증가하며, K > 0이고 현재 조각 크기가 0이 아닐 때만 카운트합니다.
3. 구현:
   - 초콜릿 크기는 비트 연산 또는 반복문을 통해 효율적으로 계산합니다.
   - 쪼개기 과정은 초콜릿 크기부터 시작하여 반으로 나누며 K를 줄여가는 방식으로 진행합니다.

예제 분석 (K=6)

• 초콜릿 크기: \(2^3 = 8\)
• 쪼개기:
  • 8 → 4 + 4 (1번, K=6 ≥ 4, K=6-4=2)
  • 4 → 2 + 2 (2번, K=2 ≥ 2, K=2-2=0)
• 출력: 8 2

---

전체 코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;

int main(void)
{
    long long k;
    cin >> k;

    long long choco = 1;
    while (choco < k)
        choco *= 2;

    int cnt = 0;
    long long current = choco;

    while (k > 0)
    {
        if (k >= current)
            k -= current;

        current /= 2;
        if (k > 0 && current > 0)
            cnt++;
    }
    
    cout << choco << " " << cnt << endl;

    return 0;
}

코드 설명

• 입력: K를 입력받습니다.
• 초콜릿 크기: choco를 1부터 시작하여 K 이상이 될 때까지 2배로 늘립니다.
• 쪼개기 횟수:
  • current를 초콜릿 크기(choco)부터 시작하여 반으로 나눕니다.
  • K ≥ current이면 current를 사용하고 K를 줄입니다.
  • K > 0이고 current > 0일 때만 쪼개기 횟수(cnt)를 증가시킵니다.
  • K=0이 되면 종료합니다.
• 출력: 초콜릿 크기(choco)와 쪼개기 횟수(cnt)를 출력합니다.

---

결론

이 코드는 백준 2885번 문제를 효율적으로 해결합니다. 초콜릿 크기를 K 이상인 최소 2의 제곱수로 설정하고, K를 만들기 위해 필요한 최소 쪼개기 횟수를 계산하는 로직을 구현하였습니다. K=6, K=10, K=7 등 다양한 테스트 케이스에서 올바른 결과를 출력하며, 시간 제한(1초)과 메모리 제한(128MB)을 만족합니다. 이 접근법은 K의 이진 표현과 쪼개기 과정의 특성을 활용하여 간단하고 직관적으로 문제를 해결합니다.