[백준] 1034번 : 램프

1034번: 램프

---

이 문제를 보고 실제로 불을 껏다 켰다 할 생각을 하니 막막했었는데.. 그런 생각을 한 것 자체가 너무 1차원적이어서 다른 분의 풀이를 참고하였다. 역시나 스위치를 올렸다 내렸다 하는 일은 존재하지 않았고 패턴을 찾는 것이 관건이었다.

 

먼저 모든 행을 돌며 각 행에 포함된 0(off)의 개수를 센다. 당연히 0의 개수는 K보다 작거나 같아야 한다. 그 행의 불을 켜려면 0의 개수가 K개 보다 많으면 안되니 말이다.

 

그리고 이것이 중요한데 K가 짝수라면 0의 개수도 짝수이어야 하고, 홀수라면 0의 개수도 홀수여야한다. 각 전구는 On/Off 상태를 갖을 수 있는데, 스위치를 홀수번 키면 상태가 바뀌지만, 짝수번 키면 상태가 그대로 유지된다.

 

이 조건이 충족되었다면 다시 모든 행을 돌며 현재 행과 같은 행을 찾는다. 여기서 현재 행과 같다는 것은 0과 1의 위치와 개수가 모두 완벽히 일치하는 것 이다.

# Code </>

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

public class Main {

    static char[][] map = new char[51][51];

    static boolean isEqual(char[] arr1, char[] arr2, int m){

        for(int i=1; i<=m; i++)
            if(arr1[i] != arr2[i])
                return false;

        return true;
    }

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

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        for(int i=1; i<=n; i++){
            char[] str = br.readLine().toCharArray();

            for(int j=1; j<=m; j++)
                map[i][j] = str[j-1];
        }

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

        /* 모든 행(Row)을 돌며 '0'의 개수 count */
        for(int i=1; i<=n; i++){

            int zero = 0;

            for(int j=1; j<=m; j++)
                if(map[i][j] == '0') zero++;

            int onRow = 0; //불이 켜진 행의 개수
            /* 0의 개수가 k이하 and 0의 개수, k가 모두 짝수? 홀수? */
            if(zero <= k && zero % 2 == k % 2){

                /* 현재 행(i)과 같은 행(같은 패턴)이 있으면 onRow 증가 */
                for(int j=1; j<=n; j++)
                    if(isEqual(map[i], map[j], m))
                        onRow++;

                max = Math.max(max, onRow);
            }

        }
        System.out.println(max);
    }
}

 

# Reference

공대생의 개발PATH님의 Tistory