백준 1034 램프 Python

🐸 문제 정보

1034번: 램프

 

🤖 알고리즘

브루트포스

(라고 적혀있지만 사실상 구현)

 

⏱️ 풀이 시간

38.51m

 

📝 풀이

처음에 문제 이해를 잘못했다.

스위치를 그냥 단순히 껐다 키는 문제라고 생각하고... 5분만에 풀면서 골드 4가 왜이리 쉽지? 생각했다.

1번 테케부터 틀리는거 보고... 아..

풀이법은 아래와 같다.

1. 첫 번째 행 부터 탐색하며, 아래 조건을 만족하면 해당 행은 스위치 조작으로 밝힐 수 있는 행이다.
   • 행 속 0의 개수가 k보다 작다.
   • 행 속 0의 개수와 k가 홀짝이 같다. (둘다 홀수거나 둘다 짝수)
2. 만약 스위치 조작으로 밝힐 수 있는 행이라면, 해당 행과 같은 행의 개수를 찾는다.
   • 이 떄 visited로 방문 처리를 하면 좋다.

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline

n, m = list(map(int, input().rstrip().split()))
bulbs = [input().rstrip() for _ in range(n)]
k = int(input().rstrip())
visited = [False] * n
res = 0

for i in range(n):
    if not visited[i]:
        visited[i] = True
        zero = bulbs[i].count('0')
        if (zero <= k) and (zero % 2 == k % 2):
            temp = 1
            for j in range(i + 1, n):
                if (not visited[j]) and (bulbs[i] == bulbs[j]):
                    visited[j] = True
                    temp += 1
            res = max(res, temp)

print(res)