[JAVA] 백준 1034 램프

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

문제분석

가로로 111111...와 같이 모든 수가 1로 바뀌어야 켜졌다 라고 한다고 한다. 버튼을 누르면 해당 열 의 모든 숫자가 바뀐다(1과 0 서로 치환).

역시 간단한 방법인 모든 경우를 탐색하려고  하니, 신경써야 할 반례가 너무 많았다.

 

다른 방법이 있나 찾다가, 이전 문제에서 사용했던, 순차적으로 탐색하면서 최대값을 저장하고, 최댓값보다 큰 경우에 최댓값을 갱신하는 방법을 사용하기로 하였다. 램프가 켜지고 꺼지면서 완성되는 열의 수를 각각 파악해야 한다(실제로 숫자를 변경하면, 시간복잡도에서 탈락).

해결과정

중복이 가능하므로, K의 갯수와 한 행의 0의 갯수의 홀수 짝수 여부가 같아야 한다(다른 경우, 무조건 한번 더 눌러야 하므로 1111...이 깨짐).

또한, K보다 한 행의 0의 갯수가 작아야 0을 1로 만들 수 있다.

한 행 기준, 다른 행들을 탐색하며 패턴(010111... 과 같은 형태)이 같고, 위의 조건들을 만족하는 경우 sameP변수를 올려서 count를 최신화하는 방식으로 문제를 해결하였다.

 

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int row = Integer.parseInt(st.nextToken());
        int col = Integer.parseInt(st.nextToken());
        int[][] arr = new int[row][col];
        for (int i = 0; i < row; i++) {
            String temp = br.readLine();
            int a = 0;
            for (String s : temp.split("")) {
                arr[i][a++] = Integer.parseInt(s);
            }
        }
        int k = Integer.parseInt(br.readLine());
        int count = 0;
        for (int i = 0; i < row; i++) {
            int zero = 0;
            int sameP = 0;
            for (int j = 0; j < col; j++) {
                if (arr[i][j] == 0) {
                    zero++;
                }
            }
            if (zero <= k && zero % 2 == k % 2) {
                for (int j = 0; j < row; j++) {
                    if (same(arr[i], arr[j], col)) sameP++;
                }
            }
            count = Math.max(count, sameP);
        }
        bw.write(String.valueOf(count));
        bw.flush();
    }

    public static boolean same(int[] a, int[] b, int col) {
        for (int i = 0; i < col; i++) {
            if (a[i] != b[i]) return false;
        }
        return true;
    }
}