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

 

문제

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

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

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

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

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

입력

첫째 줄에 K가 주어진다. (1 ≤ K ≤ 1,000,000)

출력

첫째 줄에는 상근이가 구매해야하는 가장 작은 초콜릿의 크기와 최소 몇 번 쪼개야 하는지를 출력한다.

예제 입력 1 

6

예제 출력 1 

8 2

 

 

단순 구현 문제입니다.

맨 처음 쉬프트 연산으로 배열에 2의 제곱들을 입력될 수 있는 최대값까지 넣어줍니다.

값을 입력 받고 최소 크기를 구해줍니다.

 

최소 크기는 입력 값 이상일 것이기에

2의 제곱으로 맞아 떨어지면 자신을

아니면 배열에서 최소 값을 가져와 줍니다.

 

이후 재귀함수에 최소 값을 갖고 있는 인덱스와 몇 번 쪼개는지를 나타내는 카운트 변수를 넣어줍니다.

 

배열의 현재 인덱스 값을 K에서 빼주면 언젠가는 0이 될겁니다.

이 점을 이용해 K가 0이 될때까지 재귀형식으로 함수를 돌려주고

 

주의할 점은 인덱스 값이 K이하 이어야 한다는 겁니다.

K보다 큰데 빼버리면 문제에서 요구되는것과 다르기에 조건문으로 해결하고

 

재귀 탈출 조건문으로는 i값 예외처리(안해도됨), K가 0일 때로 해주면 됩니다.

#include <iostream>

using namespace std;

#define MAX 1000000

int arr[21];
int K;

void solve(int i, int &cnt) {
  if (i < 0 || K == 0) {
        return;
    }

    if (arr[i] <= K) {
        K -= arr[i];
    }
    if (K) {
        solve(i - 1,++cnt);
    }
}

int FindIndex(int K) {
  int i = 0;

  for (; arr[i] < K; i++)
    ;
  return i;
}

int main() {
    int cnt = 0, leastSize;
  
    cin >> K;
    arr[0] = 1;
    for (int i = 1;; i++) {
        int n = 1 << i;
        arr[i] = n;
        if (n > MAX) { break; }
    }

    int idx = FindIndex(K);
    leastSize = arr[idx];

    if (arr[idx] != K)
        solve(idx, cnt);
    cout << leastSize << " " << cnt << endl;
    return 0;
}