BOJ 24982 - Alchemy

BOJ 24982 - Alchemy

처음엔 모든 out degree=0 인 원소들까지 분해를 한 후에 거기서 $\text{Min}_{i=1}^n \left\lfloor \dfrac{have_i}{need_i} \right\rfloor$ 를 따지려 했지만, 이 방법은 반례가 있다.

애초에 $N$을 만드는데 쓰이지 않는 $a_i$가 있는데 그걸 원래대로라면 할 수 없는 연산인 분해를 통해 다른 $a_j\,(j < i)$ 를 키워줘서 계산한다는 건 불가능하다.

$a_i \le 10^4$ 임을 관찰한다.

$O(n^2 \cdot \text{Max}(a_i))$ 에 풀 수 있다.

모든 레시피는 항상 $L$이 재료들보다 크므로 DAG처럼 생각해줄 수 있다.

$N$부터 시작해서 필요한걸 쭉 내려보내면서 $a_i$ 보다 현재 필요한게 이하라면 그냥 $a_i$를 다 써주고 아니면 $a_i$ 만큼 써주고 나머지는 다른 재료들에 하청을 맡긴다.

이게 가능한 이유는 항상 어떠한 metal 에 대해 최대 한 가지의 조합법밖에 없기 때문이다.

그러다 조합법이 없는 재료를 만났는데 하청을 내려줘야 하는 상황이 된다면 더 이상 못만드는 상황이 되므로 반복문을 탈출한다.

void solve() {
   int n;
   cin >> n;
   vi a(n);
   fv(a);
   int k;
   cin >> k;
   vvi edges(n);
   for (int i = 0; i < k; i++) {
      int l, m, t;
      cin >> l >> m;
      l--;
      while (m--) {
         cin >> t;
         t--;
         edges[l].pb(t);
      }
   }
   int ans = a[n - 1];
   a[n - 1] = 0;
   while (1) {
      vi need(n);
      int can = 1;
      for (int i: edges[n - 1])need[i]++;
      for (int i = n - 2; i >= 0; i--) {
         assert(need[i] >= 0);
         if (need[i] > 0) {
            if (a[i] >= need[i]) {
               a[i] -= need[i];
               continue;
            } else {
               int removed = min(a[i], need[i]);
               a[i] -= removed;
               need[i] -= removed;
               if (!sz(edges[i])) {
                  can = 0;
                  break;
               }
               for (int j: edges[i]) {
                  need[j] += need[i];
               }
            }
         }
      }
      if (!can) break;
      ans++;
   }
   cout << ans;
}