문제

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

이해

직사각형 보드의 각 셀에는 램프가 있다. 각 램프의 상태는 켜지고 꺼진 상태가 존재한다. 램프는 보드의 각 열 아래에 있는 스위치로 조작할 수 있다. 단, 스위치는 위치한 열의 모든 램프를 끄고 켠다. 켜진 램프는 꺼지고 꺼진 램프는 켜진다.

K번 스위치를 눌러 모든 램프가 켜진 행의 개수의 최댓값을 구해야 한다.

접근

문제를 요약하자면 초기 상태를 보고 스위치를 조작해 행을 탐색해야 한다.

브루트 포스로 접근해보자. 스위치는 M이 50일 때 최대이다. 누르는 횟수는 K로 최대 1000이다. 그렇다면 경우의 수는 50^1000으로 불가능한 가짓수가 나온다.

더 좋은 방법이 있을까? 있긴 있다. 스위치는 토글 방식이기 때문에 열을 기준으로 봤을 때 존재할 수 있는 패턴은 열당 2가지 밖에 없다. 따라서, 경우의 수를 2^50으로 줄일 수 있다. 하지만 이 역시 불가능한 가짓수이다.

브루트 포스가 안될 때는 문제의 특성을 파악하는 것이 중요하다. 관점을 바꿔서 행을 기준으로 문제를 바라보자.

위와 같은 보드가 있다고 가정하자. (1은 켜짐, 0은 꺼짐) 최댓값은 3이다. 행을 기준으로 '001' 패턴을 가진 행이 3개이기 때문이다. 행의 패턴은 중요한 의미를 가진다. 1행, 2행처럼 패턴이 다른 경우 어떻게 스위치를 조작해도 같은 모양이 나오지 않는다. 패턴이 같다는 뜻은 조작했을 때 서로 같은 패턴으로 변함을 의미한다.

결국, 행을 기준으로 봤을 때 같은 패턴의 갯수가 몇 개인지가 정답이 되는 문제이다. 단, 우리는 스위치를 K번 눌러야 하기 때문에 K에 대해 가능한 행의 패턴인지 확인해야 한다.

일단, 0의 개수는 모든 램프를 켜기 위한 최소 값이다. 0의 개수가 K보다 작아야 한다. 또, 다음처럼 K - (0의 개수)가 홀수라면 해당 패턴은 불가능하다.

풀이

        // count zero
        for (int i = 0; i < N; i++) {
            board[i] = br.readLine();
            for (int j = 0; j < M; j++) {
                if (board[i].charAt(j) == '0') {
                    zeroCountArr[i]++;
                }
            }
        }

0의 개수를 위처럼 단순하게 셌다.

        // check board
        int max = 0;
        for (int i = 0; i < N; i++) {
            if (zeroCountArr[i] <= K && (zeroCountArr[i] - K) % 2 == 0) {
                int sameRawCnt = 1;
                for (int j = 0; j < N; j++) {
                    if (j == i)
                        continue;

                    if (board[i].equals(board[j])) {
                        sameRawCnt++;
                    }
                }

                max = Math.max(max, sameRawCnt);
            }
        }

이제 각 행을 탐색하면 가능한 패턴인지 확인한다. 설명대로 K보다 작거나 같으며 차이가 짝수가 되어야 한다. 가능하다면 전체 보드에 같은 패턴인 행의 개수를 센다. 그 때의 개수를 max로 갱신한다.

탐색에 필요한 시간복잡도는 1000 x 1000 = 1,000,000 이 된다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class App {
    static int N, M;
    static String[] board;
    static int[] zeroCountArr;
    static int K;
    static StringTokenizer st = null;

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // input
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        board = new String[N];
        zeroCountArr = new int[N];
        // count zero
        for (int i = 0; i < N; i++) {
            board[i] = br.readLine();
            for (int j = 0; j < M; j++) {
                if (board[i].charAt(j) == '0') {
                    zeroCountArr[i]++;
                }
            }
        }

        K = Integer.parseInt(br.readLine());

        // check board
        int max = 0;
        for (int i = 0; i < N; i++) {
            if (zeroCountArr[i] <= K && (zeroCountArr[i] - K) % 2 == 0) {
                int sameRawCnt = 1;
                for (int j = 0; j < N; j++) {
                    if (j == i)
                        continue;

                    if (board[i].equals(board[j])) {
                        sameRawCnt++;
                    }
                }

                max = Math.max(max, sameRawCnt);
            }
        }

        System.out.println(max);
    }
}