백준 6233, Sweeping
USACO March 2007 Contest Gold 3번 문제.
해당 길이만큼 구간의 비트들을 전부 flip 하면 $O(N^3)$ 이 되어 시간 초과가 된다.
구간 시작이나 끝에 표시를 하며 stack 을 유지하는 유형의 기법들에 익숙해져야 한다.
길이 $N$ 인 구간 처리를 $O(N)$ 에 하는 방법을 찾아야 이런 문제들을 풀 수 있다.
해결 방법을 좀 더 구체적으로 생각해서 정밀하게 구현하는 연습을 해야한다.
Source Code
//BOJ 6233
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
int N;
bitset<5050> input, cowface;
int farr[5050];
int cowflip(bitset<5050>& cface, int len, int flips) {
int flipcnt = 0, flipcarry = 0 ;
// flipcnt : 지금까지 flip 한 총 횟수
// flipcarry : i 번째 소를 flip 해야하는 횟수
memset(farr, 0, sizeof(farr));
for (int i = 0; i <= N - len; ++i) {
if ((flipcarry + cface[i]) % 2) {
farr[i] = 1;
++flipcnt;
//소가 B 면 뒤집고, flipcnt 추가. farr 에 뒤집었다고 표시.
}
flipcarry += farr[i];
if (i - len + 1 >= 0) flipcarry -= farr[i - len + 1];
// 이전 구간에 의해 뒤집힌 횟수는 빼줘야 한다.
}
for (int i = N - len + 1; i < N; ++i) {
if ((flipcarry + cface[i]) % 2) return -1;
if (i - len + 1 >= 0) flipcarry -= farr[i - len + 1];
}
return flipcnt;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> N;
int longestbcnt = 0, tcnt = 0;
for (int i = 0; i < N; ++i) {
char C;
cin >> C;
if (C == 'F') {
input[i] = 0;
}
else {
input[i] = 1;
}
}
int fcnt, lcnt;
fcnt = INT_MAX, lcnt = -1;
for (int i = N; i >= 1; --i) {
cowface = input;
int t = cowflip(cowface, i, 0);
if (t == -1) continue;
if (fcnt > t) {
fcnt = t;
lcnt = i;
}
else if (fcnt == t && lcnt < i) {
lcnt = i;
}
break;
}
printf("%d %d\n", lcnt, fcnt);
return 0;
}