BOJ 1034 - 램프

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

1차 시도

처음 그리디를 이용하여 0의 개수가 가장 많은 열을 스위치 작동시키는 방법을 구상했다.
O(N*M)이 걸렸지만 스위치 작동 후의 0을 구하는 과정과 켜진 행을 찾는 구간 때문에 시간 초과가 발생했다.

더 빠른 방법을 구상해보기로 했다.

2차 시도

우선 규칙이 보였다.

1. 한 행에서 0의 개수가 k보다 크면, 해당 행은 완전히 켜질 수 없다.
2. 한 행의 0의 개수와 k의 홀짝이 다르면, 해당 행은 완전히 켜질 수 없다.

2번의 경우, 밑에 예시로 보자

3 3
010
101
101
4

일 경우, 2번째 열을 홀수번 킬 때 2,3번 행이 완전히 켜지게 된다.
그러나 k가 짝수이기 때문에 2,3번 행은 처음과 같은 상태가 된다.

3 3
010
101
101
3

반면, k가 홀수가 되는 경우 2,3번 행은 전과 다르게 켜질 수 있게 된다.

결론적으로 위 두 가지에 부합하는 경우, 켜질 수 있는 행의 갯수는 완전히 같은 행들의 개수 이다.
따라서, 두 조건에 부합하는 행과 같은 행의 개수가 가장 큰 것이 답이 된다.

코드

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>
#include <queue>

#define ll long long

using namespace std;

int n,m,k;
string arr[51];
priority_queue<pair<int,int>> pq;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> m;
    for(int i=0;i<n;i++) {
        cin >> arr[i];
    }
    cin >> k;

    int res = 0;
    for(int i=0;i<n;i++) {
        int tmp=0;
        for(int j=0;j<m;j++) {
            if(arr[i][j] == '0')    tmp++;
        }

        if(tmp%2 == k%2 && k >= tmp) {
            int ttmp=0;
            for(int k=0;k<n;k++) {
                if(arr[i]==arr[k])  ttmp++;
            }
            res = max(res, ttmp);
        }
    }

    cout << res;

    return 0;
}