[백준 2138번] 전구와 스위치 (Python/파이썬)

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

2138번: 전구와 스위치

아주 유명한 well known 문제이다.

예전에 플레티넘 문제인 불 끄기에서 한번 접해봤던 문제이다.

그때 1열의 경우의 수에 대해서 1024가지를 고려했었다면 여기서는 첫번째 전구를 켜냐 끄냐로 나누어서 경우를 따져주어야한다.

여기서는 첫번째 전구 on off에 대한 것만 고려하면 되므로(2가지) 어렵지 않다.

그리고 앞의 전구가 만들려고 하는 전구와 다르면 버튼을 눌러주면 된다.

그냥 문자열로 간단하게 구현해도 되지만, 그냥 본인은 비트마스킹을 사용했다.

코드는 다음과 같다.

 

import sys
input = sys.stdin.readline
n = int(input())
bulb = list(map(int,input().rstrip()))
want = list(map(int,input().rstrip()))
cnt = 0

def flip_bits(num):
    flipped_num = num ^ 1
    return flipped_num

first_on = []
for i in range(len(bulb)):
  first_on.append(bulb[i])
first_on[0] = flip_bits(first_on[0]); first_on[1] = flip_bits(first_on[1])

def turn(bulb):
  global cnt
  for i in range(1,n):
    if bulb[i-1] != want[i-1]:
      for j in range(i-1,i+2):
        try:
          bulb[j] = flip_bits(bulb[j])
        except:
          pass
      cnt += 1
    if bulb == want:
      print(cnt)
      sys.exit()

turn(bulb)
cnt = 1
turn(first_on)
print(-1)

 

 

 

한줄평: 웰논 그리디