13134번: Baseball Watching

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


$O(?)$

9회까지 선생님이 취할 수 있는 이동 가지수는 3^9이다.
각 경우마다 선생님을 한 번도 만나지 않을 방법 2^9가지를 모두 조사한다.

#include<cstdio>
int n, c[19683], mini = 1e9, maxi;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int t = 0;
        for (int j = 0, x; j < 9; j++) scanf("%d", &x), t = t * 3 + x - 1;
        c[t]++;
    }
    for (int i = 0; i < 19683; i++) {
        int s = 0;
        for (int j = 0; j < 1 << 9; j++) {
            int t = 0;
            for (int k = 0, ti = i, tj = j; k < 9; k++, ti /= 3, tj /= 2) t = t * 3 + (ti % 3 + tj % 2) % 3;
            s += c[t];
        }
        if (mini > s) mini = s;
        if (maxi < s) maxi = s;
    }
    printf("%d %d", mini, maxi);
    return 0;
}