[PS] BOJ2138 전구와 스위치 ( greedy ) With 파이썬

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

2138번: 전구와 스위치

 

◎ 문제풀이

 

 

 

 

이 문제는 어렵게 느껴진다.

 

현재를 목표로 만드는데 한 개의 스위치가 여러 개의 전구에 영향을 주어, 경우를 복잡하게 만들기 때문이다. n번 스위치를 눌러 n번 전구를 목표와 일치시켰는데, n+1 스위치가 눌리면 다시 원위치이다. 

 

그러므로 위 문제는 복잡하게 얽힌 경우를 얼마나 단순히 풀어낼 수 있는가를 묻는 문제이다. 경우를 나누어 보자.

 

1) 첫 번째 버튼이 눌린 경우

 

 

 

첫 번째 버튼이 눌렸다고 '가정'해버리면, 첫 번째 전구에게 영향을 주는 두 번째 스위치 하나뿐이다. 두 번째 스위치를 누를지 말지에 따라 첫번째 전구가 결정된다. 

 

그러므로

만약 첫 번째 전구가 목표와 일치하면 두번째 스위치를 안 누르고

만약 첫 번째 전구가 목표와 일치하지 않으면 두번째 스위치를 누르면 된다. ( 그럼 첫 번째 전구는 목표와 일치 )

 

이는 현재에 따라 최상의 로직을 따르는 그리디 알고리즘이다.

 

두 번째 전구도 마찬가지이다. 

두 번째 전구에 영향을 주는 스위치는 세번째 스위치뿐이다. ( 두 번째 스위치는 이미 누를지/안누를지 결정했음 )

 

이렇듯 첫 번째 경우를 '가정'으로 고정하면 전구에 영향을 주는 스위치가 하나만 남게된다. 이후 그리디 알고리즘으로 풀면된다. 

 

 

2) 첫 번째 버튼이 안 눌린 경우

 

 

 

 

 

첫 번째 버튼이 안 눌렸다고 '가정'하고 풀면, 전구 하나에 영향을 주는 스위치는 하나만 존재하게 된다. 

 

1)과 2) 중 현재를 목표로 만드는데 최솟값을 구하면 된다. 둘 다 목표로 만들지 못하면 -1을 출력한다.

 

 

◎코드

#BOJ2138 전구와 스위치 
import sys
input = sys.stdin.readline

n = int(input())
light = list(map(int,input().rstrip("\n"))) # 현재
target = list(map(int,input().rstrip("\n"))) # 목표

def change(light,target) :
  count = 0
  for i in range(1,n) :
    #이전 전구가 같은 상태인 경우 넘기기 ( greedy )
    if light[i-1] == target[i-1] : continue
      
    #이전 전구가 다른 상태인 경우 스위치 버튼 누르기
    count += 1
    for j in range(i-1,i+2) : 
      if j < n : light[j] = 1 - light[j]

  return count if light == target else 1e9

# 첫번째 스위치를 누르지 않은 경우
ans = change(light[:],target)

# 첫번째 스위치를 누른 경우
light[0] = 1 - light[0]
light[1] = 1 - light[1]
ans = min(ans,change(light[:],target)+1) # 두 경우 중 최솟값 구하기
print( ans if ans != 1e9 else -1)