[PS|애드훅] 백준 1034 램프

문제

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

1034번: 램프

---

첫번째 풀이 - 백트래킹, 시간초과

N, M의 입력값이 50이라 불안하긴 했지만 일단 백트래킹 말고는 최적화 방법을 못 떠올렸다.
아래와 같이 백트래킹으로 진입하며 XOR로 한 줄씩 램프를 반대로 설정하도록 구현하였다.

"""켜져있는 램프는 꺼지고, 꺼져있는 램프는 켜진다"""
N, M = map(int,input().split())
List = []
for _ in range(N):
    List.append(list(list(input())))
K = int(input())
answer = 0

for i in range(N):
    for j in range(M):
        List[i][j] = int(List[i][j])

while K>M :
    K-=2

def back(arr, K, visited):
    #print(arr, K, visited)
    global answer

    if K%2 == 0: #K가 짝수면 갱신해도 괜찮다.
        temp = 0
        for i in range(N):
            if 0 not in arr[i]: temp+=1
        answer = max(answer, temp)
    if K==0: #더이상 할 수 없음
        return
    for i in range(M):
        if not visited[i]:
            for j in range(N):
                arr[j][i]=(arr[j][i])^1
            visited[i]=1
            back(arr, K-1, visited)
            visited[i]=0
            for j in range(N):
                arr[j][i]=(arr[j][i])^1


visited = [0 for _ in range(M)] #어떤 열을 선택했는가
back(List, K, visited)
print(answer)

답은 도출이 되나 시간초과..

---

결국 알고리즘 유형을 보았으나 브루트포스, 애드훅 으로 나와있어 일단 답을 보기로 했다.

만약 램프 모양이 아래와 같다고 하면

001
010
010

1번째와 3번째 열을 XOR 형태로 바꾸면 2번째와 3번째 행이 모두 1이 되어 최대 2개까지 가능해진다.

100
111
111

이 때 한 행을 모두 1로 바꾸려면, 한 행에서의 0의 갯수를 zero_count  라고 할 때 당연히 zero_count  <=K 이어야 할 것이고, 같은 행을 두 번 바꾸어 K-=2 시킬 수 있을 것이므로 zero_count == (K-2 or K-4 or K-6 ...) 일 것이다.
따라서  zero_count  <=2 이면서 zero_count % 2 == K % 2 이면 이 행을 모두 켤 수 있다.

아래와 같이 행에 대해 조건을 탐색하며 '이 행과 똑같은 모양을 가진 행'을 찾는 부분이 브루트포스, 애드훅 부분이다.

# 입력받기
n, m = map(int, input().split())
lst = []
for _ in range(n):
    lst.append(input())

k = int(input())

max_cnt = 0

for col in range(n): #각 행에 대해 0의 갯수 탐색
    zero_count = 0
    for num in lst[col]:
        if num == '0':
            zero_count += 1

    # 이 행과 똑같은 값을 가진 행의 개수 찾기
    same_col_cnt = 0
    if zero_count <= k and zero_count%2 == k%2:  # 이 행을 모두 켤 수 있는가
        for col2 in range(n):
            if lst[col] == lst[col2]:
                same_col_cnt += 1

    max_cnt = max(max_cnt, same_col_cnt)

print(max_cnt)