백준 2885 - 초콜릿 식사

문제 설명

학교 근처 편의점에 새 초콜릿이 들어왔다. 이 초콜릿은 막대 모양이고, 각 막대는 정사각형 N개로 이루어져 있다. 초콜릿의 크기(정사각형의 개수)는 항상 2의 제곱 형태이다. 즉, 1, 2, 4, 8, 16, ...개의 정사각형으로 이루어져 있다.

상근이는 점심식사로 초콜릿을 먹는다. 이때, 적어도 K개 정사각형을 먹어야 남은 수업을 졸지 않고 버틸 수 있다. 상근이의 친구 선영이도 초콜릿을 좋아한다. 선영이는 초콜릿은 돈을 주고 사기 아깝다고 생각하기 때문에, 상근이가 주는 초콜릿만 먹는다.

상근이는 막대 초콜릿를 하나 산 다음에, 정확하게 K개 정사각형이 되도록 초콜릿을 쪼갠다. K개는 자신이 먹고 남는 것은 선영이에게 준다.

막대 초콜릿은 나누기 조금 어렵게 되어 있어서, 항상 가운데로만 쪼개진다. 즉, 정사각형이 D개 있는 막대는 D/2개 막대 두 조각으로 쪼개진다.

K개 정사각형을 만들기 위해서, 최소 몇 번 초콜릿을 쪼개야 하는지와 사야하는 가장 작은 초콜릿의 크기를 구하는 프로그램을 작성하시오. 상근이는 초콜릿을 하나만 살 수 있다. 꼭 한 조각이 K개일 필요는 없고, 여러 조각에 있는 정사각형을 합쳤을 때 K개이면 된다.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 초콜릿을 K개 먹어야 할 때, 전체 초콜릿의 개수와 이를 자르는 횟수를 최소한으로 만들어야 한다.

이때, 초콜릿은 2의 제곱으로만 존재할 수 있으며 이를 자를 때는 절반으로 잘라야 한다.

 

우선, 문제를 두 가지로 분리할 수 있다.

• 전체 초콜릿 구하기
• 자른 횟수 구하기

 

K개를 넘는 최소 크기의 전체 초콜릿의 크기를 구하는 것은 쉽다.

K보다 크거나 같을 때까지 2를 계속 곱하면 된다.

int total = 1;
while (total < K)
{
    total *= 2;
}

 

자른 횟수를 구하는 방법은 초콜릿의 크기가 K보다 작다면 K에서 그만큼 뺀다.

만약, K보다 크다면 초콜릿을 절반으로 자른다.

또한, 전체 초콜릿의 크기가 K와 동일하다면 한 번도 자르지 않아야 하기 때문에 예외적으로 처리한다.

if (total == K)
{
    cout << total << " " << 0;
}
else
{
    int temp = total;
    int ans = 0;

    while (K > 0)
    {
        if (K >= temp)
        {
            K -= temp;
        }
        else
        {
            temp /= 2;
            ans++;
        }
    }

    cout << total << " " << ans;
}

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <list>
#include <bitset>

using namespace std;

int K;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout.precision(4);

    cin >> K;

    int total = 1;
    while (total < K)
    {
        total *= 2;
    }

    if (total == K)
    {
        cout << total << " " << 0;
    }
    else
    {
        int temp = total;
        int ans = 0;

        while (K > 0)
        {
            if (K >= temp)
            {
                K -= temp;
            }
            else
            {
                temp /= 2;
                ans++;
            }
        }

        cout << total << " " << ans;
    }

    return 0;
}

---