CodeForce - Phoenix and Science(1348D)

문제(링크)

mass의 크기는 절반으로 쪼개져도 결국 총 합은 같으므로 소수점을 고려할 필요가 없었습니다.
즉, 하루가 지날 때마다 +1 씩 늘어나는 것만 고려하면 됩니다.

박테리아가 가장 최대로 번식할 경우는
1 -> 2 -> 4 -> 8 -> 16 ....
0 1    2    3    4  .... day
위와 같이 증가하는데, 2day엔 최대 7까지 만들 수 있고, 3day엔 최대 15까지 만들 수 있습니다.
즉, N이 어느 구간에 있는지에 따라 day를 고정할 수 있습니다.
N 이 8~15 일 땐 3day, 16~31 일 땐 4day 등등...

day를 고정하면 그리디하게 풀이할 수 있습니다.
하루가 지날 때마다 현재 박테리아 수를 N에서 뺴주는데,
현재 박테리아 수를 구할 때 둘 중 한가지로 고릅니다.
1. (남은 N) / (남은 일 수)
2. 1에서 구한 박테리아 수를 전 날 박테리아로 만들 수 없을 때 -> 만들 수 있는 최대 박테리아를 구해야 하므로 2를 곱해줍니다.

늘어난 박테리아 - 원래 박테리아를 매번 출력해줍니다.
모든 N에 대해 구할 수 있으므로 -1을 출력할 필요가 없었습니다.

#include<iostream>
#include<algorithm>
#include<math.h>
#include<string>
#include<vector>
#include<queue>
using namespace std;
#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pii pair<int, int>
#define ll long long

int T, N;

int main(void) {
 FIO;

 cin >> T;

 while (T--) {
  cin >> N;
  int day = 0;
  int temp = N;

  while (temp / 2 != 0) {
   temp /= 2;
   day++;
  }

  int BC = 1;
  N -= 1;

  string ans = "";
  ans += to_string(day) + "\n";

  for (int i = 0; i < day; i++)
  {
   int left = day - i;
   int maximum = N / left;
   int ori_BC = BC;

   if (BC * 2 < maximum) {
    //maximum만큼의 박테리아를 만들 수 없을때
    BC *= 2;
   }
   else
    BC = maximum;
   N -= BC;
   ans += to_string(BC - ori_BC) + " ";
  }

  
  if (N == 0)
   cout << ans;
  else
   cout << "-1\n";
  cout << "\n";
 }
}