문제

지민이는 각 칸마다 (1*1크기의 정사각형) 램프가 들어있는 직사각형 모양의 탁자를 샀다. 모든 램프는 켜져있거나 꺼져있다. 각 열의 아래에는 스위치가 하나씩 달려있는데, 이 스위치를 누를 때마다 그 열에 있는 램프의 상태가 바뀐다. (켜져있는 램프는 꺼지고, 꺼져있는 램프는 켜진다)

만약 어떤 행에 있는 램프가 모두 켜져있을 때, 그 행이 켜져있다고 말한다. 지민이는 스위치를 K번 누를 것이다. 서로다른 스위치 K개를 누르지 않아도 된다. 지민이는 스위치를 K번 눌러서 켜져있는 행을 최대로 하려고 한다.

지민이의 탁자에 있는 램프의 상태와 K가 주어졌을 때, 스위치를 K번 누른 후에 켜져있는 행의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. N은 행의 개수이고, M은 열의 개수이다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 램프의 상태가 주어진다. 1이 켜져있는 상태이고, 0이 꺼져있는 상태이다. 마지막 줄에는 K가 주어진다. K는 1,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 문제의 정답을 출력한다.

접근 과정

격자판의 상태가 주어지고 열단위로 On, Off 하며 격자의 상태를 확인하는 문제이다. N과 M의 크기가 작아 완전탐색을 사용할까 하였으나 상태가 바뀔 떄 마다 격자를 확인해야하니 실행 시간을 초과하지 않을까 걱정되어 다른 방법을 고민해보았다.
종이에 격자판을 그려가며 몇가지 규칙을 발견하였다.
- 동일한 열을 짝수번 누르면 기존과 동일한 상태로 돌아온다.
- 짝수번 버튼을 눌렀을 때는 꺼진 램프의 갯수가 짝수인 행만 켜져있는 행이 될 수 있고 홀수번 버튼을 눌렀을 때는 꺼진 램프의 갯수가 홀수인 행만 켜져있는 행이 될 수 있다.
- 격자의 상태가 동일하지 않은 행들은 동시에 켜져있는 행이 될 수 없다.

이러한 규칙에 따라 불필요하게 K번 버튼을 누른 것에 대해 전부 확인할 필요 없이 처음 주어진 격자 상태만으로도 문제의 답을 도출해낼 수 있다. 램프가 꺼진 갯수가 홀수/짝수개인 행끼리 분류하고 그 중 동일한 패턴을 가진 행의 최댓값을 구하면 된다. 행끼리의 비교는 memcmp() 함수를 쓰면 편하다.

깔끔한 코드는 아니지만 규칙이 확실하여 어렵지 않게 구현할 수 있었는데 다 풀고보니 이게 웬걸, 다른 사람의 코드를 보니 재귀호출을 통한 완전탐색으로 잘 풀고 있었다 하핫

소스 코드

#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

#define OFF '0'

int main(void) {
    int N, M, K;
    vector<int> evenOffindexes, oddOffindexes;
    char board[55][55];
    int rowOffCounts[55];
    bool bVerified[55];
    
    memset(bVerified, 0, sizeof(bVerified));

    cin >> N >> M;

    for (int i = 0; i < N; ++i) {
        rowOffCounts[i] = 0;

        // 한 행을 입력 받고
        for (int j = 0; j < M; ++j) {
            cin >> board[i][j];
            if (board[i][j] == OFF) {
                ++rowOffCounts[i];
            }
        }

        // 꺼진 램프 갯수가 홀수인지 짝수인지 검사
        if (rowOffCounts[i] & 1) {
            oddOffindexes.push_back(i);
        } else {
            evenOffindexes.push_back(i);
        }
    }
    cin >> K;

    vector<int>& indexes = K & 1 ? oddOffindexes : evenOffindexes;
    int maxDupNum = 0;
    
    // 동일한 패턴의 행을 찾고 그 최대치를 기록
    for (unsigned int i = 0; i < indexes.size(); ++i) {
        int dupNum = 1;
        if (bVerified[i] || rowOffCounts[indexes[i]] > K) {
            continue;
        }

        for (unsigned int o = i + 1; o < indexes.size(); ++o) {
            if (bVerified[o]) {
                continue;
            }

            if (memcmp(board[indexes[i]], board[indexes[o]], M) == 0) {
                bVerified[o] = true;
                ++dupNum;
            }
        }
        bVerified[i] = true;

        if (dupNum > maxDupNum) {
            maxDupNum = dupNum;
        }
    }

    cout << maxDupNum << endl;

    return 0;
}