[백준] 1034번 램프(java)

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

1034번: 램프

핵심

처음에 이 문제를 완전탐색을 해야 하는 줄 알았다.

하지만 시간복잡도에서 터지게 된다. 이 문제는 실제 스위치를 켜고 끄는 것이 아닌 행의 패턴을 비교하는 작업이 필요하다.

어떠한 패턴과 같은 행이 있다면 스위치를 눌렀을 때 모두 똑같이 변하게 된다. 이를 이용해서 풀어야 한다.

 

 

정답 코드

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

public class Main{
    static int[][] map = new int[51][51];
    static int count;
    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] nAndM = br.readLine().split(" ");
        int n = Integer.parseInt(nAndM[0]);
        int m = Integer.parseInt(nAndM[1]);

        for (int i = 1; i <= n; i++){
            String[] info = br.readLine().split("");
            for (int j = 1; j <=m; j++){
                map[i][j] = Integer.parseInt(info[j-1]);
            }
        }

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

        for (int i = 1; i <= n; i++){

            int zeroCount = 0;

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

            int samePattern = 0;

            if (zeroCount <= k && zeroCount%2 == k%2){
                for (int j = 1; j<= n; j++){
                    if (isSame(map[i],map[j],m))samePattern++;
                }
            }
            count = Math.max(count, samePattern);
        }
        System.out.println(count);
    }
    public static boolean isSame(int[] arr , int[] arr2,int m){

        for (int i = 1; i<=m; i++){
            if (arr[i] != arr2[i])return false;
        }
        return true;
    }
}

해설

우선 전구를 map 배열에 넣는다.

이후 처음부터 마지막 열까지 패턴을 비교하게 된다.

중요한 점은 0의 개수가 k개 이하면 전부 1로 바꿀 수 없게 된다.

또한 k가 홀수인데, 0의 개수는 짝수라면 전부 1로 바꿀 수 없다.

따라서 k와 0의 개수는 %2의 결과가 같아야 한다.

이후 다른 열을 비교하여 전체의 행과 같은 패턴이 있다면 카운트를 증가시킨다.

 

 

 

배운 점

문제를 읽자마자 자연스럽게 완전탐색을 시도하려 하였다. 문제를 영리하게 푸는 방법을 익히는 것이 중요하고,

풀이를 하기 전에 시간복잡도를 꼭 생각해야겠다. 잘못된 풀이로 시작하게 된다면,

중간에 말리는 일이 생기기 때문에 이를 주의해야겠다.