[백준]JAVA - 1034번: 램프

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

1034번: 램프

풀이

문제를 읽은 직후에 이해가 잘 되지 않았다. 문제 내용은 아래와 같다.

1. 가로 x 세로 크기의 map에 램프가 있다.

2. 각 열의 맨 아래에 해당 열의 램프를 단 번에 키고 끌 수 있는 스위치가 존재한다.

3. 마지막 입력에 스위치를 누를 수 있는 횟수 K가 주어진다.

 

스위치를 K번 눌러서 각 행의 모든 램프가 켜진 행을 최대한 많이 만들면 된다.

예제 1번을 보면서 문제를 풀어보겠다.

위의 그림은 예제 1번의 초기 상태이다.

스위치를 누를 기회는 총 1번으로 모든 램프가 켜진 행을 최대한 많이 만들려면 두 번째 열의 스위치를 눌러야한다.

 

두 번째 열을 누르면 위와 같은 상태로 총 2개의 행을 만들 수 있다.

 

이제 문제가 조금 이해가 되었는가? 그렇다면 모든 램프가 켜진 행을 최대한 많이 구하려면 어떻게 해야할까?

스위치를 눌렀을 때 해당 열의 모든 램프가 변한다.

 

이걸 생각해보면 모든 전구가 켜진 행은 처음부터 서로 동일한 형태를 가지고 있다. 를 추리할 수 있다.

즉, 동일한 형태의 행이 많을수록 정답일 확률이 높다.

 

또한, 동일한 형태가 많은 행의 '0' 의 개수가 K번 보다 많다면 모든 램프를 킬 수 없고, '0'의 개수와 K의 수의 홀짝이 같아야한다.

 

결론은 3가지의 조건을 만족해야한다.

1. 동일한 형태의 행이 많은 게 정답일 확률이 높다.
2. '0'의 개수가 K번 보다 적어야한다.
3. '0'의 개수와 K의 홀짝이 같아야한다.

<최종코드>

import java.io.*;
import java.util.*;
 
public class Main {
    static int N, M;
    static int[][] map;
    static boolean[] visited;
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
		
        int ans = 0;
        N = Integer.parseInt(st.nextToken()); // 행
        M = Integer.parseInt(st.nextToken()); // 열
		
        map = new int[N][M];
		
        for (int i=0; i<N; i++) {
            String str = br.readLine();
            for (int j=0; j<M; j++) {
                map[i][j] = str.charAt(j) - '0';
            }
        }
		
        int K = Integer.parseInt(br.readLine()); // 스위치를 누를 수 횟수
        visited = new boolean[N]; // 방문 여부
        for (int i=0; i<N; i++) {
            if (visited[i]) continue;
			
            visited[i] = true;
			
            // 행마다 0의 개수 구하기
            int OffRamp = 0; 
            for (int num : map[i]) {
                if (num == 0) {
                    OffRamp++;
                }
            }
			
            // 같은 모양의 행 개수 찾기
            int SameRowCnt = find(i);
			
            // K와 0의 개수의 홀짝이 같고, K가 같거나 클 경우
            if (K % 2 == OffRamp % 2 && K >= OffRamp) {
                ans = Math.max(ans, SameRowCnt);
            }
        }
		
        System.out.println(ans);
    }
	
    public static int find(int row) {
        int cnt = 0;
		
        // 같은 행 비교
        for (int i=0; i<N; i++) {
            if (Arrays.equals(map[i], map[row])) {
                visited[i] = true;
                cnt++;
            }
        }
		
        return cnt;
    }
}

내가 생각한 시간 복잡도: O(NM)