[백준] 1034 램프

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

 

아이디어

01

10

10 에서

 

2번째 행의 0을 키게 되면 해당 열의 모든 비트가 반전되므로

 

00

11

11 이 되어서

 

답이 2가 된다.

 

열 전체가 바뀌므로, 동일한 비트의 개수가 중요하다고 생각했다.

 

어떤 자리의 비트를 키는 횟수는 k번 정의 되므로

반드시 k번의 열 반전이 일어난다.

그럼 결국 동일한 비트의 개수 중에 최대인 것을 뽑고

그게 k번 안에 모두 1로 바꿀 수 있는지 판별하면 된다.

1.dict를 통해서 각 행의 비트의 중복되는 수를 세어 준다.

2. 0의 개수를 세어준다. (p라고 하자)

3. p가 짝수면 k도 짝수여야 하고, p가 홀수면 k도 홀수여야 한다.

4. p는 k보다 작거나 같아야 한다.

 

n,m = map(int, input().split())

bits = dict()

lights = [input() for _ in range(n)]

c = int(input())

for i in lights:

    if i in bits:

        bits[i] += 1

    else:

        bits[i] = 1

ans = 0

for k,v in bits.items():

    p = k.count('0')

    if p % 2 == c % 2 and p <= c:

        ans = max(ans, v)

print(ans)