[백준] 1034. 램프

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

1034번: 램프

처음에는 완전 탐색으로 m개의 열 중 k번 스위치를 눌러 켜진 행의 갯수를 구하려고 했다. 그런데 이렇게 하면 m개의 열 중 중복을 허용하여 k개를 고르는 것이기 때문에 m^k (50 ^ 1000)으로 시간초과가 날 것이다. 

 

주요 포인트는 다음과 같다.

• 행 단위로 생각해보자. 하나의 행을 모두 1로 만들어야 켜진 행이 된다. 
• (1) 만약 하나의 행에 0의 갯수가 k보다 크면, 그 행은 절대 켜진 행이 될 수 없다.
• (2) 또한 하나의 행에 0의 갯수가 짝수인데 k가 홀수이면, 그 행은 절대 켜진 행이 될 수 없다.
• (3) 마찬가지로 하나의 행에 0의 갯수가 홀수인데 k가 짝수이면, 그 행은 절대 켜진 행이 될 수 없다.
• 위 3가지 조건을 만족하는 행이면, 모든 행을 탐색하며 자신과 같은 행을 찾으면 된다. 즉, k번 0 -> 1로, 1 -> 0으로 변경하며 스위치를 누르는 행위를 할 필요가 없고, 처음부터 같은 모양의 행들의 갯수가 켜진 행의 갯수가 된다. 그리고 그 갯수들의 최댓값이 정답이 된다. 
• 결론은.. 직접 일일이 구현해볼 필요가 없으며, 켜진 행이 될 수 있는 조건을 찾고, 그 조건과 함께 맞는 행의 갯수를 찾으면 된다. 
• 어려운 문제였지만, 주요 포인트만 잘 잡으면 됐었다. 어렵더라도 문제의 포인트를 잘 찾아보자..!

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

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int n;
    static int m;
    static int k;
    static int[][] map;
    static int answer;

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new int[n][m];
        for (int i = 0; i < n; i++) {
            String[] arr = br.readLine().split("");
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(arr[j]);
            }
        }

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

        for (int i = 0; i < n; i++) {
            int zeroCnt = 0;
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 0) {
                    zeroCnt++;
                }
            }

            // 조건 1. 하나의 행에서 0의 개수가 k개 초과이면 켜진 행이 될 수 없음
            // 조건 2. k와 0의 개수가 둘 다 홀수이거나 짝수이어야 함
            if (zeroCnt <= k && zeroCnt % 2 == k % 2) {
                int sameCnt = 0;
                for (int j = 0; j < n; j++) {
                    if (isSame(map[i], map[j])) {
                        sameCnt++;
                    }
                }
                answer = Math.max(answer, sameCnt);
            }
        }

        System.out.println(answer);
    }

    private static boolean isSame(int[] arr1, int[] arr2) {
        for (int i = 0; i < m; i++) {
            if (arr1[i] != arr2[i]) return false;
        }
        return true;
    }
}