[백준 C++] 2885번 - 초콜릿 식사

문제 소개

 

2885번: 초콜릿 식사

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

 

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

 

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

 

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

 

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

 

 

 

 

---

문제 풀이 전략

 

기획

 

 이 문제는 엄청나게 간단하게 풀이할 수 있다.

 

 우선 k개의 초콜릿 정사각형을 먹기 위해서는 사온 초콜릿의 수가 k 보다 크거나 같아야 한다. 이때 사온 초콜릿의 개수는 반드시 2의 제곱수이다. 숫자가 아주 크다면 효율적인 알고리즘을 고려해보아야 하나, 이 문제는 기껏해야 100만밖에 되지 않으므로 무식하게 1부터 시작하여 k 보다 크거나 같은 제곱수를 브루트포스 방식으로 찾아내면 된다.

 

 그다음으로 몇번을 나누어야 하는지를 구하여야 한다. 이것 또한 무식하게 구할 수 있다. 이진수로 나타내었을 때, 가장 마지막에 오는 1의 자릿수 - 1을 출력하기만 하면 된다.

 

 쉽게 설명하여 숫자 6을 이진수로 나타내면 "0110"인데, 마지막으로 오는 1의 자리수는 앞에서부터 세 번째 자리이므로, 2번 나눈다가 정답이다. "110"이 아닌 "0110"인 이유는 반드시 구매한 초콜릿의 길이가 2의 제곱수 이기 때문에, "1", "10", "100", "1000"... 의 형태를 지니고 있기 때문이다. 이 구매한 초콜릿의 길이와 자릿수를 맞춰 주어야 한다.

 

 다른 예시로 숫자 8을 이진수로 나타내면 "1000"이고, 마지막으로 오는 1의 자리수는 앞에서부터 첫 번째 자리이므로, 0번 나눈다가 정답이다. 숫자 5를 이진수로 나타내면 "0101"이고, 마지막으로 오는 1의 자릿수는 앞에서부터 네 번째 자리이므로, 3번 나눈다가 정답이다.

 

 

 

---

소스 코드

 

#include <iostream>
using namespace std;

void scanData();
void solveProblem();
void printAnswer();

int k;
int choco = 1;
int division = 0;

int main()
{
    scanData();
    solveProblem();
    printAnswer();

    return 0;
}

void scanData()
{
    scanf("%d", &k);
}

void solveProblem()
{
    while(choco < k)
        choco *= 2;

    int tmp = choco;
    int cnt = 0;
    while(k != 0)
    {
        if(k >= tmp)
        {
            division = cnt;
            k -= tmp;
        }
        tmp = tmp / 2;
        cnt += 1;
    }
}

void printAnswer()
{
    printf("%d %d\n", choco, division);
}

 

 

 

---

테스트 케이스

 

[예제 1]
입력:
6

출력:
8 2



[예제 2]
입력:
4

출력:
4 0



[예제 3]
입력:
5

출력:
8 3