[백준][1034] 램프

• Problem Link : https://www.acmicpc.net/problem/1034

문제

• 열마다 램프를 끼고 클 수 있는 버튼이 있다.
• 최대한 많은 행을 버튼을 K번 눌러서 키려고 한다.
• 킬 수 있는 최대한 많은 행을 구하시오.

입력

• 첫째 줄, N과 M이 주어진다.
• 둘째 줄, N개의 줄에 램프의 상태가 주어진다.
• 마지막 줄, K가 주어진다.

출력

• 셋째 줄, 행의 최대값을 출력한다.

풀이

행의 개수가 50개보다 적기 때문에 하나의 행을 모두 킨다고 가정하도 해당 행을 켰을때 같이 켜지는 똑같은 행의 개수를 찾으면 될 것이라고 생각할 수 있다.

K가 1000까지 올 수 있기 때문에 K를 이용한 반복문으로 푸는 문제는 아니라는 것을 알 수 있다.

이 문제의 주목해야하는 점은 K번을 무조건 눌러야한다는점이다. 즉, 만약 K가 홀수라면 0이 홀수 개수인 행만 킬 수 있고 K가 짝수이면 0이 짝수인 행만 킬 수 있다. 따라서 다음과 같은 과정으로 정답을 찾을 수 있다. 추가적으로 0이 K보다 많은 행은 절대 모든 행의 램프를 켤 수가 없다는 점도 처리를 해주어야한다.

예를 들어 "000"처럼 0이 세 개이면, 버튼을 세번, 다섯번, 일곱법, 이렇게 홀수 번 눌러야만 모두 킬 수 있다. 전원이 켜진 램프를 2번씩 더 눌러서 껐다 킬 수 있기 때문이다.

1. 1번행부터 모든행을 방문하면서 반복한다.
2. 방문한 행의 0의 갯수를 모두 센다.
3. 만약 0이 K보다 많다면 모든 0을 키는것이 불가능하므로 스킵한다.
4. K가 홀수이면 0이 홀수인 행만, K가 짝수이면 0이 짝수인 행만 대상으로 진행한다.
5. 방문한 행을 K번 눌러 모두 켰다고 가정하고 방문한 행과 똑같은 행이 있는지 모든 행을 대상으로 수행한다.
   • 자기 자신도 어차피 COUNT 해줘야 하기 때문에 자기 자신도 방문해야 한다.
6. 기준이 되는 행과 똑같은 행의 갯수를 모두 센 후 최대 COUNT와 비교해서 최대값을 설정한다.

쉽게 말해 입력이 50개의 행밖에 되지 않으니깐 1번행을 모두 켰을때 같이 모두 켜지는 1번행과 똑같은 행을 모두 비교하는 방식으로 50개의 행을 모두 반복한다.
시간 복잡도가 결국 O($N^2$)이기 때문에 입력이 커지면 실행 시간 초과가 발생할 것이다.

코드

import sys

input = sys.stdin.readline

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

arr = []
for _ in range(n):
    arr.append(input().strip())
k = int(input())

max_cnt = 0

for i in range(n):
    zero = 0
    for c in arr[i]:
        if c == "0":
            zero += 1
    cnt = 0
    if zero <= k and zero % 2 == k % 2:
        for j in range(n):
            if arr[i] == arr[j]:
                cnt += 1
    max_cnt = max(max_cnt, cnt)
print(max_cnt)