[백준 2885] 초콜릿 식사

우선 초콜릿 크기는 무조건 2의 거듭제곱으로 시작한다.

그리고 초콜릿을 자를때는 무조건 반으로 자른다.

따라서 자른 초콜릿이 1일때 빼고는 홀수가 나올 수 없다.

그래서 N이 홀수면 무조건 끝까지 잘라야한다.

 

이제 조금 애매한 것이 짝수이다.

 

애매한 경우는 이런 경우를 생각해볼 수 있다

 

만약 10일 예로 든다면

 

10 = 8 + 2

10 = 4 + 4 + 2

 

이렇게 두 가지 경우를 생각해볼 수 있다.

 

이 중 어느 것이 더 적게 초콜릿을 자르는 경우인지 알아야하는데

일단 2의 거듭제곱이 아닌 수이면 무조건 기존 크기를 절반으로 자른 것은 필요로 한다.

왜냐하면 10은 2의 거듭제곱인 8이랑 16 사이인데 10이 8보다는 크고 16을 2로 나누면 8이기 때문이다.

 

즉 2의 거듭제곱이 아닌 짝수인 N은 무조건 기존 사이즈의 절반은 필요로 한다.

따라서 생각할때 남은 반쪽을 어떻게 잘라서 N을 만드느냐만 생각해주면 된다.

 

그 남은 반쪽을 어떻게 잘라서 N을 만드느냐는 브루트포스로 했다.

어차피 선형시간이라 시간제한에 안걸린다.

 

#include <iostream>
#include <math.h>

using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int N; cin >> N;

	int size = 1;
	int cnt = 0;

	while (size < N) {
		size *= 2;
		cnt++; // 제곱한 횟수
	}

	if (size == N) {
		cout << size << " " << 0;
		return 0;
	}

	// 홀수면 무조건 끝까지 잘라야함
	if (N % 2 == 1) {
		cout << size << " " << cnt;
	}
	// 짝수면 브루트포스 O(N) 선형시간
	else {
		int x = cnt;
		while (N > 0) {
			x--;
			if (N - pow(2, x) >= 0) { N -= pow(2, x); }
		}
		cout << size << " " << cnt - x;
	}

	return 0;
}