Nebius Welcome Round (Div. 1 + Div. 2) - D. Accommodation (2000)
모든 층을 독립적으로 생각할 수 있다.
어떤 층에 대해 최소값을 찾는다고 생각해보자.
그럼 인 부분을 최대한 하나의 방으로 묶는것이 최적이다. 으로 묶을 수 있는 개수를 라 하자.
두 개로 묶을 수 있는 방이 정확히 개 라는 제한때문에 항상 개의 방을 두 개로 묶을 수 있다.
그럼 의 개수를 라 한다면 정답은 이다.
최대값을 찾는다고 생각해보자.
동일하게 이아닌 이 하나혹은 하나도 없는 부분으로 묶을 수 있는 개수를 라 하자.
그럼 어쩔수없이 으로 묶어야 하는 것의 개수는 이고,
나머지는 모두 방 하나에 하나씩 묶을 수 있으므로 정답은 이다.
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;
}
Comments