BOJ 14222 - 배열과 연산

BOJ - 배열과 연산

오름차순으로 정렬하고 작은 수부터 계속해서 채워야할 수를 채워준다.

만약에 현재 자리가 이미 채워져있다면 그리디하게 수를 k만큼 계속 증가시킨다.

딱 현재 보고 있는 숫자보다 크거나 같을 때 까지만 증가시켜두면서

수 $x$가 몇개 있는지 가져가면 된다.

void solve() {
   int n, k;
   cin >> n >> k;
   vi a(n);
   fv(a);
   sort(all(a));
   vi cnt(100);
   for (int i: a) cnt[i]++;
   for (int i = 1; i <= n; i++) {
      for (int j = 1; j < i; j++) {
         int c = cnt[j];
         int diff = (i - j + k - 1) / k * k;
         cnt[j + diff] += c;
         cnt[j] = 0;
      }
      if (!cnt[i]) {
         cout << 0;
         return;
      } else {
         cnt[i]--;
      }
   }
   cout << 1;
}