백준 1034 : 램프 c++

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

1034번: 램프

설명
1. 동시에 행에 불이 들어올 조건은 행의 패턴이 동일해야한다.
ex) 1011 과 1001은 절대로 같이 켜질수가 없음
2. 해당 패턴의 0의개수보다 k가 작으면 절대로 해당 패턴에서는 불을 킬 수 없다.
3. 불을 키고 남은 횟수가 홀수라면 하나의 열은 반드시 불이 꺼지게 되므로 불을 킬 수 없게 된다.

 

m이 50까지 이므로 패턴을 2^50미만의 수로 나타낼 수 있다. => long long으로 표현 가능
map을 이용해 패턴의 개수를 구하고 해당 패턴의 0의 개수로 행에 불을 킬 수 있는지를 판별하고 킬 수 있다면 최대값을 갱신한다.

 

#include<bits/stdc++.h>
#include<time.h>


#define MAX 1000000007
#define INF 2000000000
#define MOD 1000000007 
using namespace std;
typedef long long ll;
typedef pair<int, int > pii;
typedef pair<long long, long long> pll;
typedef pair<double, double> pdd;

int dx[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };
int dy[8] = { 1, -1, 0, 0, -1, 1, 1, -1 };

/*
int dx[2][6] = {
    {1, -1, 0, 0 ,1, -1},
    {1, -1, 0, 0, -1, 1}
};
int dy[2][6] = {
    {0, 0, 1, -1 ,1, -1},
    {0, 0, 1, -1, 1, -1}
};*/

//int dx[8] = { -1, -1, 1, 1, -2, -2, 2, 2 };
//int dy[8] = { 2, -2, 2, -2, -1, 1, -1, 1 };

void init() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
}
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }


int main() {
    init();
    int n, m; cin >> n >> m;
    map<ll, int> pattern;

    for (int i = 0; i < n; i++) {
        string s; cin >> s;
        ll num = 0;
        ll cnt = 0;
        for (int i = 0; i < m; i++) {
            num *= 2;
            if (s[i] == '1') 
                num += 1;
        }
        pattern[num]++;
    }
    int k; cin >> k;
    int ans = 0;
    for (auto iter = pattern.begin(); iter != pattern.end(); iter++) {
        ll num = iter->first;
        int cnt = 0;
        for (ll i = 0; i < m; i++) {
            if (!(num & 1ll << i))
                cnt++;
        }
        if (k >= cnt && (k - cnt) % 2 == 0) {
            ans = max(ans, iter->second);
        }
    }
    cout << ans << "\n";

}