6233번: Face The Right Way

https://www.acmicpc.net/problem/6233


$O(n^2)$

임의의 k에 대해 기계의 최소 작동 횟수는 그리디 알고리즘을 통해 O(n)에 구할 수 있다.

k가 정해지면 앞의 소부터 보면서 뒤돌아 있는 경우 그 뒤 k마리의 방향을 바꿔주면 된다. 이를 빠르게 처리하기 위해 prefix sum과 비슷하게 기계의 누적 작동횟수와 이후 기계가 작동을 멈출 시점을 저장해준다.

#include<cstdio>
int n, k, m = 1e9;
char d[5000];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf(" %c", d + i);
    for (int i = 1; i <= n; i++) {
        int cnt = 0, t = 0, j = 0, s[5001] = {};
        for (; j < n; j++) if ((t ^= s[j]) ^ d[j] == 'B') {
            if (j + i>n) break;
            cnt++;
            t ^= 1;
            s[j + i]++;
        }
        if (j == n && m>cnt) m = cnt, k = i;
    }
    printf("%d %d", k, m);
    return 0;
}