1034 램프 (Java)

램프

문제

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

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

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

입력

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

출력

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

풀이

이 문제의 핵심은 스위치를 누르면 한 열의 램프들이 커지거나 켜지고, 확인할 때는 행을 확인한다.
예를들어 3번째 열에 있는 스위치를 누른다면 모든 행의 3번째 위치에 있는 값이 바뀌게 된다.
그러므로 특정 열에 있는 스위치를 눌렀을 때의 총 켜져있는 행을 구하기 위해서는 열의 값이 같은 행을 구해야 한다.
이 말은 같은 모양의 행을 많이 가질수록 답이 커질 수 있다.

그리고 중요한 점은 몇가지 더 있다.
특정 행을 지정했을 때 이 행을 모두 키기 위해서는 그 행이 가지고 있는 0의 수만큼 스위치를 눌러야 한다.
또한 모두 키기 위해서는 가지고 있는 0의 수의 짝,홀수 여부와 누를 수 있는 스위치 수 K의 짝,홀수 여부와 같아야한다.
예를 들면 어떤 행이 0을 2(짝수)개 가지고 있는데 스위치를 3(홀수)번 눌러야 한다면 어떤 수는 다시 0이 되어버리기 때문이다.

즉 정리하자면 조건은 다음과 같다.

1. 어떤 행 A가 가지고 있는 0의 수는 눌러야 하는 K번보다 작거나 같아야 한다.
2. 1번을 만족하며 A가 가지고 있는 0의 수는 K와 같은 짝,홀수를 가져야 한다.
3. 1,2 번을 만족하는 A와 똑같이 생긴 행의 갯수를 세어 그 최댓값을 찾아야 한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class Main{

    static int n;
    static int m;
    static int[][] graph;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");

        n = Integer.parseInt(input[0]);
        m = Integer.parseInt(input[1]);

        graph = new int[n][m];

        String[] strings = new String[n];


        for (int i = 0; i < n; i++) {
            String s = br.readLine();
            strings[i] = s;
            for (int j = 0; j < m; j++) {
                graph[i][j] = s.charAt(j) - '0';
            }
        }

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

        boolean[] isOk = new boolean[n];

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

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

            if ((cnt % 2) == (k % 2) && cnt <= k) { // 1,2번 조건 검사
                isOk[i] = true;
            }


        }

        int ans = 0;

        for (int i = 0; i < n; i++) {
            int cnt = 0;
            if (isOk[i]) {
                for (int j = 0; j < n; j++) {
                    if (strings[i].equals(strings[j])) { // 3번 조건을 위해 동일한 값 찾기
                        cnt++;
                    }
                }
            }

            if (ans < cnt) { // 최댓값 비교
                ans = cnt;
            }
        }

        System.out.println(ans);
    }
}

회고

너무 어려웠다. 이게 골드 5라니....
처음에는 감도 안잡혀 일단 문제 이해를 위해 시간초과인것은 알지만 어떻게든 풀어볼까 하여 백트레킹으로 풀어봤다.
K의 수가 크므로 당연히 시간초과가 발생했다.
다음으로 dp로도 생각을 해봤는데 어림도 없었다. ㅋㅋㅋㅋㅋㅋㅋ
그래서 결국 구글링을 통해 정답을 찾아봤다.
정말 생각지도 못한 풀이방식을 발견하고 살짝 현타가 왔다.
그래도 골5 정도 문제는 풀 수 있겠다 싶었는데 이 문제를 풀며 부족함을 많이 느꼈다.
꾸준히 문제를 풀며 사고력을 기르자!!