[BOJ] 1034번 램프 (Java)

백준 1034 램프

수의 범위가 50이었고 전체 경우의 수는 2^50으로 완전 탐색으로 해결할 수 없는 문제였다. 모든 경우가 독립적이지 않다고 생각하고 완전 탐색으로 해결하려 했지만, 잘못된 생각이었다. 단순 구현으로 해결하려 한 코드이다. 당연하게도 시간 초과였다.

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

public class Main {
    static int n, m, p, maxV = 0, k;
    static int[][] arr;

    static void pushSwitch(int j){
        for(int i = 0; i < n; i ++){
            arr[i][j] *= -1;
        }
    }

    static int check(){
        int res = 0;
        for(int i = 0; i < n; i++){
            int sum = 0;
            for(int j = 0; j < m; j++){
                sum += arr[i][j];
            }
            if(sum == m){
                res += 1;
            }
        }
        return res;
    }
    
    static void dfs(int ptr, int cnt){
        if(ptr == m){
            if (cnt % 2 == p){
                maxV = Math.max(check(), maxV);
            }
        } else {
            dfs(ptr + 1, cnt);
            if(cnt < k){
                pushSwitch(ptr);
                dfs(ptr + 1, cnt + 1);
                pushSwitch(ptr);
            }
        }
    }
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringTokenizer st = new StringTokenizer(br.readLine());
            String tmp;
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            arr = new int[n][m];
            for(int i = 0; i < n; i++){
                tmp = br.readLine();
                for(int j = 0; j < m; j++){
                    if(tmp.charAt(j) == '1'){
                        arr[i][j] = 1;
                    } else{
                        arr[i][j] = -1;
                    }
                }
            }
            k = Integer.parseInt(br.readLine());
            p = k % 2;
            dfs(0 , 0);
            System.out.println(maxV);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

램프의 특징은 다음과 같다.

1. 모든 행은 서로 독립적이다 즉, 위 아래 행이 서로 영향을 받지 않는다.
2. 0의 개수뿐만 아니라 위치도 중요하다.
3. 서로 다른 모양의 행이 동시에 조건을 만족할 수 없다. 즉 한 가지 모양의 행만 선택해야 한다.

위 특징들을 토대로 알고리즘을 수정했다.

1. 완전 탐색은 최대 2^50의 경우로 불가능하다.
2. 모든 행의 모양은 독립적이므로 Hash를 활용한다.
3. 각 행과 동일 한 행의 개수, 필요한 0의 개수가 필요하므로 HashMap을 활용한다.
4. 0의 개수는 k를 2로 나눈 나머지와 같아야 가능하고 k보다는 작아야 한다.

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

public class Main {

    public static void main(String[] args) {
        try {
            int n, m, k, s, cnt, maxV;
            int [] tmpList = new int [2];
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            HashMap <String, int[]> hm = new HashMap<>();
            StringTokenizer st = new StringTokenizer(br.readLine());
            String tmp;
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());

            // 0 갯수 확인 후, HashMap에 0 갯수와 같은 라인 갯수
            for(int i = 0; i < n; i++){
                tmp = br.readLine();
                cnt = 0;
                for(int j = 0; j < m; j++){
                    if(tmp.charAt(j) == '0'){
                        cnt++;
                    }
                }
                if(hm.containsKey(tmp)){
                    tmpList = hm.get(tmp);
                    hm.replace(tmp, new int[] {tmpList[0] + 1, tmpList[1]});
                } else{
                    hm.put(tmp, new int[]{1, cnt});
                }
            }
            k = Integer.parseInt(br.readLine());

            // 2로 나눈 나머지값 확인
            s = k % 2;
            maxV = 0;
            for(String key : hm.keySet()){
                tmpList = hm.get(key);
                if(tmpList[1] <= k && tmpList[1] % 2 == s){
                    maxV = Math.max(maxV, tmpList[0]);
                }
            }
            System.out.println(maxV);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}```