[백준] 10765 Bessie Gets Even

B E S I E G O M 7가지 문자에 최대 20개의 가중치가 들어온다

그 때 (B+E+S+S+I+E)*(G+O+E+S)*(M+O+O)가 짝수인 

경우의 수를 찾는 문제다

처음에 생각을 하고 한심한 방법같아서 코딩을 안하다가

설마하고 해봤는데 맞았다..!

근데 맞는 방법인지는 모르겠따

먼저 3개의 곱이 짝수라는 얘기는 하나만 짝수면 된다는 얘기다

하나만 짝수면 곱했을 때 무조건 짝수다

그래서 한덩어리씩 보며 짝수가 되는 경우의 수를 찾았다

1) BESSIE에서는 E와 S가 짝수개 이므로 B+I가 짝수인 경우만 세면 된다

2) GOES 에서는 B+I가 홀수인 경우 * (G+O+E+S)가 짝수인 경우를 센다

3) MOO 에서는 (B+I 홀수) * (G+O+E+S 홀수) *(M이 홀수)를 센다!

이렇게 더하면 답나온다!

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int arr[26],ans,cnt=1;
int main() {
    arr['B' - 'A'] = 0; arr['E' - 'A'] = 1;
    arr['S' - 'A'] = 2; arr['I' - 'A'] = 3;
    arr['G' - 'A'] = 4;  arr['O' - 'A'] = 5;
    arr['M' - 'A'] = 6;
    vector<vector<int>> vt(10);
    int n; scanf(" %d", &n);
    for (int i = 0; i < n; i++) {
        char a; int x;
        scanf(" %c %d", &a, &x);
        vt[arr[a - 'A']].push_back(x);
    }
    for (int i = 0; i < 7; i++) cnt *= vt[i].size();
    cnt /= vt[0].size(); cnt /= vt[3].size();
    int sum = vt[0].size() * vt[3].size(), even = 0;
    for (int i = 0; i < vt[0].size(); i++) {
        for (int j = 0; j < vt[3].size(); j++) {
            if ((vt[0][i] + vt[3][j]) % 2 == 0) even++;
        }
    }
    ans += cnt*even;
    sum -= even; even = 0;
    int sum2 = vt[1].size() * vt[2].size() * vt[4].size() * vt[5].size();
    cnt /= vt[1].size(); cnt /= vt[2].size(); cnt /= vt[4].size(); cnt /= vt[5].size();
    for (int i = 0; i < vt[1].size(); i++) {
        for (int j = 0; j < vt[2].size(); j++) {
            for (int k = 0; k < vt[4].size(); k++) {
                for (int l = 0; l < vt[5].size(); l++) {
                    if ((vt[1][i] + vt[2][j] + vt[4][k] + vt[5][l]) % 2 == 0) even++;
                }
            }
        }
    }
    ans += (sum*even*cnt);
    sum2 -= even; even = 0;
    for (int i = 0; i < vt[6].size(); i++) {
        if (vt[6][i] % 2 == 0) even++;
    }
    ans += (sum*sum2*even);
    printf("%d\n", ans);
}