[백준] 1034 램프

1. 문제

www.acmicpc.net/problem/1034

1034번: 램프

2. 접근방법

그리디스러운 문제

백준 알고리즘 분류에는 브루트포스로 되어 있는데

아이디어를 떠올려야 하는 부분이 많다.

 

가장 중요한 내용으로는

열 단위로 숫자를 변경 할 수 있는데

행 단위로 점수를 매긴다는 것

 

여기서

A 행의 0을 모두 1로 바꿔서 점수행이 될 때

똑같이 점수행이 될 수 있는 다른 행들은

최초의 A행과 똑같은 모양이어야 한다.

 

하나라도 다른 모양이 있다면

열단위로 바뀌기 때문에

그 다른 모양은 A행이 1이 될 때 0이 될 수 밖에 없기 때문.

 

그렇다면 이제

모든 행에서 K번 안에 모두 1로 바꿀 수 있으면서

K가 짝수 홀수 인지에 대해

검사하면서 그 행이 1로 바꿀수 있는지 확인하고

 

가능하다면 그 행과 똑같은 행이 몇개인지 확인하고

 

가능한 행들 중 그 갯수가 가장 큰 것을 구하면 된다.

 

3. 자바 코드

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

public class Main {

	static int map[][];
	static int N, M, K, max;
	static boolean visit[];
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		map = new int[N][M];
		visit = new boolean[N]; 
		for (int i = 0; i < N; i++) {
			String a = br.readLine();
			for (int j = 0; j < M; j++)
				map[i][j] = Integer.parseInt(a.charAt(j) + "");
		}
		K = Integer.parseInt(br.readLine());
		find();
		System.out.println(max);
	}
	static void find() {
		for(int i = 0 ; i < N ; i++) {
			if(visit[i])
				continue;
			visit[i] = true;
			if(check(i)) {
				max = Math.max(cntsame(i),max);
			}
			
		}
	}
	static boolean check(int row) {
		int zero = 0;
		for(int i = 0 ; i < M ; i++) {
			if(map[row][i] == 0)
				zero++;
		}
		if(zero <= K && zero%2 == K%2)
			return true;
		return false;
	}
	static int cntsame(int origin) {
		int cnt = 1;
		for(int i = origin+1 ; i < N ; i++ ) {
			boolean issame = true; 
			for(int j = 0 ; j < M ; j++) {
				if(map[origin][j] != map[i][j]) {
					issame = false;
					break;
				}
			}
			if(issame) {
				visit[i] =true;
				cnt++;
			}
		}
		return cnt;
	}
	
	
}

4. 마치며

처음에 K의 갯수를 제한하는 것으로 dfs가 가능할 줄 알았는데

그래도 2^50으로 시간이 터져서 안되더라

백준 알고리즘 분류가 브루트포스로 되어 있던데

그리디스러운게 더 크지 않나 싶다.