[백준] 1034 : 램프 / python

1. 문제 설명

1034번: 램프

문제

지민이는 각 칸마다 (1×1크기의 정사각형) 램프가 들어있는 직사각형 모양의 탁자를 샀다. 모든 램프는 켜져있거나 꺼져있다. 각 열의 아래에는 스위치가 하나씩 달려있는데, 이 스위치를 누를 때마다 그 열에 있는 램프의 상태가 바뀐다. 켜져있는 램프는 꺼지고, 꺼져있는 램프는 켜진다)

만약 어떤 행에 있는 램프가 모두 켜져있을 때, 그 행이 켜져있다고 말한다. 지민이는 스위치를 K번 누를 것이다. 서로다른 스위치 K개를 누르지 않아도 된다. 지민이는 스위치를 K번 눌러서 켜져있는 행을 최대로 하려고 한다.

지민이의 탁자에 있는 램프의 상태와 K가 주어졌을 때, 스위치를 K번 누른 후에 켜져있는 행의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. N은 행의 개수이고, M은 열의 개수이다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 램프의 상태가 주어진다. 1이 켜져있는 상태이고, 0이 꺼져있는 상태이다. 마지막 줄에는 K가 주어진다. K는 1,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 문제의 정답을 출력한다.

 

2. 풀이 전 계획과 생각

• 위의 문제를 스위치를 킬 수 있는 모든 경우를 다 따져봤을 때, 중복조합으로 구하면 50^1000이므로 시간초과가 난다.
• 그러므로, 규칙을 찾아서 문제를 풀어봐야겠다는 생각이 들었다.
• 다 켜져 있는 행의 최댓값을 구하고 싶기 때문에 행 기준으로 접근했다.

 

1. 각 행마다 0의 개수를 구한다.
2. 행에서 0의 개수가 K개 이하이고, K개가 홀수이면 0의 개수도 홀수이어야 하고, K개가 짝수이면 0의 개수가 짝수일 때 다 킬 수 있는 행이다.
3. 한 행의 모든 램프를 킬 수 있는 행이라면 이 행과 똑같이 생긴 다른 행도 킬 수 있으므로 똑같은 값을 가진 행들의 개수를 구한다.

→ 모든 행마다 반복하면서 어떤 행을 킬 수 있다면 그 행과 똑같은 값을 가진 행의 개수를 세고 센 값 중 최댓값을 구하면 된다.

 

3. 풀이

N, M = tuple(map(int, input().split()))
lamps = [list(input()) for _ in range(N)]
K = int(input())

lamp_off_cnt = [0] * N
for row in range(N):
    off_cnt = 0
    for col in range(M):
        if lamps[row][col] == '0':
            off_cnt += 1
    lamp_off_cnt[row] = off_cnt

def get_same_row_cnt(row):
    result = 0
    for another_row in range(N):
        if another_row != row and lamps[another_row] == lamps[row]:
            result += 1
    return result

answer = 0
for row in range(N):
    if lamp_off_cnt[row] <= K and lamp_off_cnt[row] % 2 == K % 2:
        answer = max(answer, 1 + get_same_row_cnt(row))

print(answer)

 

4. 풀이 후 알게된 개념과 소감

• Ad-hoc 문제가 아직 낯설다.
  Ad-hoc 문제 풀 때 정렬해서 접근하는 편이었는데
  구하고자 하는 바의 기준으로 생각해보면서 문제를 해결하는 연습을 더 해봐야겠다.