[BOJ 24198 // C++] Muffinspelet

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 24198번 문제인 Muffinspelet이다.
문제는 아래 링크를 확인하자.

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

24198번: Muffinspelet

머핀을 어떤 개수로 나누어도 상대방은 둘 중 개수가 더 많거나 같은 머핀더미를 고르는 것이 항상 최선의 전략이므로, 상대방이 먹을 머핀의 개수를 최소화하기 위해서는 두 더미에 들어있는 머핀의 수가 최대한 같게, 즉 머핀이 2N개이면 N개와 N개의 머핀이 들어있는 두 더미로, 머핀이 2N+1개이면 N개와 N+1개의 머핀이 들어있는 두 더미로 나누는 것이 최선의 전략이 된다.

 

위의 과정을 반복문을 이용해 시뮬레이션하는 코드를 작성해 문제를 해결하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N;
int A, B;
int turn = 0;

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

	cin >> N;
	while (N) {
		int x = N - (N >> 1);
		if (turn) A += x;
		else B += x;
		turn ^= 1;

		N >>= 1;
	}

	cout << A << ' ' << B;
}