BOJ_1034 램프 Gold.4

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

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

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

---

이 문제를 접근할때, 먼저 시간복잡도를 생각해봤다.

N, M은 1 <= N, M <= 50 이다.
따라서 스위치가 켜지고 꺼지는 것에 대한 경우의 수는 2^50 이다.

그렇다면 브루트포스를 통해 알고리즘을 구현하면 시간초과가 난다.

따라서, 어떻게 시간 안에 문제를 풀어낼 수 있을까? 했지만 도저히 떠올릴 수 없어서 풀이를 참고했다.

1. 초기에 상태가 다른 행은 조작 횟수와 상관없이 같아질 수 없다.
2. 따라서, 하나의 행에서 0의 갯수를 확인하고 초기 상태가 같은 행의 갯수를 통해 문제를 풀 수 있다.

단, 조건이 있다.
하나의 행에서 0의 갯수가 조직 횟수인 K보다 작거나 같아야 하고
0의 갯수를 2로 나눈 나머지와 K를 2로 나눈 나머지가 같아야 한다.

그 이유는 스위치를 짝수번 눌러야 결국 처음이랑 똑같아지기 때문이다.

다양한 접근을 접해봤어야 했는데 아쉬웠다

package baekjoon;

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

public class BOJ_1034 {
    private static int N, M, K;
    private static int[][] arr;
    private static String[] temp;
    private static boolean[] check;
    private static int answer = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new int[N][M];
        temp = new String[N];
        check = new boolean[N];

        for (int i = 0; i < N; i++) {
            temp[i] = br.readLine();
            for (int j = 0; j < M; j++) {
                arr[i][j] = Character.getNumericValue(temp[i].charAt(j));
            }
        }

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

        for (int i = 0; i < N; i++) {
            int cnt = 0;

            for (int j = 0; j < M; j++) {
                if(arr[i][j] == 0) cnt++;
            }

            if ((cnt % 2 == K % 2) && cnt <= K) {
                check[i] = true;
            }
        }

        for (int i = 0; i < N; i++) {
            if (check[i]) {
                int cnt = 0;

                for (int j = 0; j < N; j++) {
                    if (temp[i].equals(temp[j])) {
                        cnt++;
                    }
                }

                if (cnt > answer) {
                    answer = cnt;
                }
            }
        }

        System.out.println(answer);
    }
}