[백준] 파이썬 1034 : 램프 (골드 4)

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

---

1. 문제 해석

행, 열에서 1은 켜진 스위치, 0은 꺼진 스위치
각 열마다 스위치가 하나씩 달려 있어 스위치를 누를 때마다 상태 바뀜
한 행이 모두 켜져있을 때 행이 켜졌다고 말함
k번 눌러서 켜져있는 행 최대

조합인가? -> 시간 오래 걸림
규칙을 찾자!
1. 특정 열의 조합은 특정 패턴의 행만 켤 수 있다
-> 패턴 개수를 세서 스위치 k번 눌렀을 때 켤 수 있는 가장 많은 패턴 구하기

2. 스위치 연속해서 누를 수 있다
k가 홀수 일때 - 0이어야 함
k가 짝수 일때 - 1이어야 함

 

2. 문제 풀이

from collections import defaultdict
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
lamps = [defaultdict(int) for _ in range(m+1)]
for _ in range(n) :
    s = input().strip()
    lamps[s.count('0')][s] += 1

k = int(input())
result = 0
for i in range(k%2, min(m+1, k+1), 2):
    for j in lamps[i].values() :
        result = max(result, j)
print(result)

---

규칙을 찾아내서 어떻게 풀 것인가를 고민해봐야했다. 다른 사람의 코드를 참고해서 풀어보았으니 다시 한 번 꼭 풀어 볼 것!!