simul.cpp

#include <cstdio>
#include <queue>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;

int depth(int a)
{
	int now = 3, res = 0, sum = 0;
	while (sum < a)
	{
		res++;
		for (int i = 0; i < now; i++) sum++;
		now *= 3;
	}
	return res;
}

int main()
{
	int hw = 100;
	for (int i = 1; i <= 50; i++) { // i는 처음 쿠키의 개수
		priority_queue<pair<int, int> > pq;
		for (int j = 1; j <= i; j++) {
			pq.push({ -(hw - i), j });
		}
		int cnt = 0;
		while (!pq.empty()) // pq에는 (-남은경로의길이, 쿠키번호) 가 들어 있음
		{
			cnt++;
			int move = depth(pq.size());
			vector<pair<int, int>> vec;
			for (int k = 0; k < move; k++) {
				auto now = pq.top(); pq.pop();
				now.first += 1;
				if (now.first != 0) vec.push_back(now);
			}
			for (auto v : vec) pq.push(v);
		}
		printf("cookie %d : move %d\n", i, cnt);
	}
}