[C++] 사각형 게임 (Small) (백준 25046번)

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

 

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    vector<vector<int>> s(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> s[i][j];
        }
    }

    int bm; // rows seleted by minwoo
    int maxi = 1 << n;
    long long maxa = LONG_LONG_MIN;

    for (int i = 0; i < maxi; i++) {
        long long ms = 0; // minwoo's score
        for (int j = 0; j < n; j++) { // col
            bm = i;
            long long off = 0;
            long long on = 0;
            for (int k = 0; k < n; k++) { // row
                if (bm % 2 == 0) off += s[k][j];
                else on += s[k][j];
                bm = bm >> 1;
            }
            // if jongjin select this col -> jongjin's score = on
            // if jongjin does not select this col -> jongjin's score = off
            if (on > off) ms += off;
            else ms += on;
        }
        if (ms > maxa) maxa = ms;
    }

    cout << maxa << '\n';
}

비트마스킹으로 풀 수 있었던 문제. 일단 민우가 선택할 수 있는 모든 경우를 생각하고, 각 경우마다 종진이 할 수 있는 최선의 선택을 했을 때의 민우의 점수를 저장하면 되는 문제였다. (정답)