Nebius Welcome Round (Div. 1 + Div. 2) - D. Accommodation (2000)

D. Accommodation

모든 층을 독립적으로 생각할 수 있다.

어떤 층에 대해 최소값을 찾는다고 생각해보자.

그럼 $11$ 인 부분을 최대한 하나의 방으로 묶는것이 최적이다. $11$ 으로 묶을 수 있는 개수를 $T$라 하자.

두 개로 묶을 수 있는 방이 정확히 $\dfrac{m}{4}$개 라는 제한때문에 항상 $\text{Min}\left( \dfrac{m}{4}, T \right)$ 개의 방을 두 개로 묶을 수 있다.

그럼 $1$의 개수를 $A$라 한다면 정답은 $A-\text{Min}(m/4, T)$ 이다.

최대값을 찾는다고 생각해보자.

동일하게 $11$ 이아닌 $1$이 하나혹은 하나도 없는 부분으로 묶을 수 있는 개수를 $T$라 하자.

그럼 어쩔수없이 $11$으로 묶어야 하는 것의 개수는 $B=m/4-T$ 이고,

나머지는 모두 방 하나에 하나씩 묶을 수 있으므로 정답은 $A-B$ 이다.

void solve() {
   int Y, X;
   cin >> Y >> X;
   int mn = 0, mx = 0;
   for (int y = 0; y < Y; y++) {
      string s;
      cin >> s;
 
      int one = cntt(s, '1');
      int oneone = 0, notoneone = 0;
      for (int i = 0; i < X - 1; i++) {
         if (s[i] == '1' && s[i + 1] == '1') {
            oneone++;
            i++;
         }
      }
      for (int i = 0; i < X - 1; i++) {
         if (!(s[i] == '1' && s[i + 1] == '1')) {
            notoneone++;
            i++;
         }
      }
      int two = min(X / 4, oneone);
      mn += two + one - two * 2;
      two = min(X / 4, notoneone);
      mx += one - (X / 4 - two);
   }
   cout << mn << ' ' << mx;
}