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

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

2885번: 초콜릿 식사

문제

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

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

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

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

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

입력

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

출력

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

---

주어진 K를 만들기 위해 가장 작은 2^N의 값과 2^N에서 K를 만들기 위해 쪼개야 하는 횟수를 알아내야 하는 문제이다.

경우의 수를 나누어 생각하면 쉽게 해결할 수 있다.

 

1. 주어진 수 K가 2^N으로 될 수 있는 경우. ex) K->16 (=2^4)
2. 주어진 수 K가 2^N으로 될 수 없는 경우
   1. 주어진 수 K가 짝수인 경우
   2. 주어진 수 K가 홀수인 경우

 

위와 같이 모든 경우의 수를 나누어준다.

해결하기 쉬운 순부터 이야기를 하자면, 

 

1번인 경우 확인할 필요도 없이 K와 0을 반환해주면 끝난다.

2번의 경우는 주어진 수 K가 2^N으로 될 수 없기 때문에 어떠한 2^N의 수를 쪼개서 만들어야한다. 그렇기 때문에 K보다는 크면서 가장 작은 2^N의 수를 찾아주어야 한다. 

 

앞으로는 K보다는 크면서 가장 작은 2^N의 수를 X라고 하겠다.

 

2-1인 주어진 수 K가 짝수인 경우는 K가 짝수이기 때문에 초콜릿을 쪼개가는 과정에서 답을 찾을 수 있다. X 또한 짝수일 수 밖에 없기 때문에 X/2의 경우도 짝수가 되어 K로 합칠 수 있다. 따라서 반복문을 통해 몇 번 쪼개야하는지 확인해가며 구할 수 있다.

int getEvenValue(int value){
	int X = value, cnt = 0;
	while(K != 0){
		if(K >= X / 2) K -= X / 2;
		X /= 2;
		cnt++;
	}
	return cnt;
}

 

2-2인 주어진 수 K가 홀수인 경우 홀수를 만들기 위해 무조건 1이 존재해야한다. 그렇기 때문에 X를 쪼개가면서 1을 무조건 만들어줘야한다. 예를 들어 K가 17인 경우 X는 32가 된다. 그럼 X를 [16, 16]으로 나눈 후 하나의 16을 1로 만들어줘야한다. 이것이 가장 적게 쪼개는 방법이 된다.

 

1) X를 [X/2, X/2]로 쪼개는 횟수 : 1번

2) X/2를 1로 만들기 위해 쪼개는 횟수 : n번

 

따라서, 2-2의 경우는 위 경우를 더한 횟수 (1+n)번이 답이 된다.

int getOddToOne(int x){
	for(int i=1;;i++){
		int power = (int)pow(2, i);
		if(power == x) return i+1;
	}
}

 위 방법은 1에서 시작하여 2^i가 X/2가 될 때 i와 X를 X/2로 나눌 때의 1번을 더해주어 (i+1)을 반환해준다.

 

위와 같이 가능한 모든 경우의 수를 나누어 코드를 작성해주면 된다.

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define INF 1e9+3
#define endl '\n'

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int K;

void input(){
	cin >> K;
}

int getPower(int x){
	for(int i=1;;i++){
		int val = (int)pow(2, i);
		if(val == x) return val;
		if(val > x) return -1;
	}
}

int getMinTwoPower(int x){
	for(int i=1;;i++){
		int power = (int)pow(2, i);
		if(x < power) return power;
	}
}

int getOddToOne(int x){
	for(int i=1;;i++){
		int power = (int)pow(2, i);
		if(power == x) return i+1;
	}
}

int getEvenValue(int value){
	int X = value, cnt = 0;
	while(K != 0){
		if(K >= X / 2) K -= X / 2;
		X /= 2;
		cnt++;
	}
	return cnt;
}

pair<int, int> solution(){
	if(getPower(K) != -1) return {K, 0};
	int value = getMinTwoPower(K);
	if(K % 2 != 0){
		return {value, getOddToOne(value/2)};
	} else{
		return {value, getEvenValue(value)};
	}
}

int main(){
	fastio;
	input();
	pair<int, int> result = solution();
	cout << result.first << " " << result.second << endl;

	return 0;
}