백준 1034 번 : 램프 - 파이썬

www.acmicpc.net/problem/1034

1034번: 램프

1034번 : 램프

알고리즘 공부를 시작한지 얼마 안되어서 생각보다 어렵게 느껴지네요. 어쨌든 제가 이해한 풀이대로 적어보도록 하겠습니다.

 

1 0 1

1 0 0

1 0 1

K=3 인 예제를 가지고 설명해보겠습니다.

 

1. 각 행마다 0의 개수를 구합니다. 예제에서는 1행은 1개, 2행은 2개, 3행은 1개가 됩니다.

 

2. (0의 개수가 K보다 작거나 같고), (K가 짝수면 0의 개수도 짝수, K가 홀수면 0의 개수도 홀수) 여야 한 행을 온전히 모두 킨 상태로 만들 수 있습니다.

 

생각해보면 당연합니다.

0의 개수가 스위치를 누르는 횟수인 K보다 많으면 절대로 꺼져있는 램프들을 다 못킵니다. 그리고 0의 개수가 1개인데 K가 2일 경우 어떤 스위치를 2번 누르던 행을 모두 킬 수 없겠죠? 따라서 (0의 개수 <= K의 개수) and (0의 개수%2 == K%2)를 만족하는 행만 행에 있는 모든 램프를 킬 수 있습니다.

 

3. 한 행의 모든 램프를 킬 수 있다면, 이 행과 똑같이 생긴 다른 행도 킬 수 있으므로 똑같은 값을 가진 행들의 개수를 구합니다. 예제에서는 첫번째 행 1 0 1은 0의 개수가 K의 개수인 3보다 작고, 0의 개수와 K가 홀수이므로 이 행은 모두 킬 수 있습니다. 따라서 값이 같은 1행과 3행을 동시에 킬 수 있습니다. 따라서 총 2개의 행을 킬 수 있습니다.

 

두번째 행을 생각해보면 K는 홀순데 0의 개수는 짝수이므로 이 행은 킬 수 없습니다.

 

이와 같이 모든 행에 대해 반복하면서 어떤 행을 모두 킬 수 있다면 그 행과 똑같은 값을 가진 행의 개수들을 세고 센 값들 중 최대값을 구하면 정답이 됩니다!

 

구현한 코드는 다음과 같습니다.

# 입력받기
n, m = tuple(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
        
    # 이 행과 똑같은 값을 가진 행의 개수 세기
    col_light_cnt = 0
    if zero_count <= k and zero_count%2 == k%2:  # 이 행을 모두 킬 수 있다면
        for col2 in range(n):  # 다시한번 행을 반복하면서
            if lst[col] == lst[col2]:  # 두 개의 행이 같으면
                col_light_cnt += 1  # 1을 더해준다
                
    max_cnt = max(max_cnt, col_light_cnt)  # 최대값보다 크면 업데이트
    
print(max_cnt)