백준 2138번 - 전구와 스위치

i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 원하는 상태를 만들기 위해 스위치를 최소 몇 번 누르면 되는지 알아내는 프로그램을 작성하시오.

# 정답 코드

스위치를 누르면 i, i-1, i+1번째의 전구 상태가 모두 변한다. 현재 i번째가 원하는 전구상태가 아니라고 누르면 i-1, i+1 모두 변하는데 그럼 i-1번째를 또 확인해야 하는가? 그렇다고 i+1번째를 생각하면서 i번째의 스위치를 누르면 i+1번째 스위치는 i+1, i+2번째 스위치에 의해 변한다. 음?
방금 한말을 반대로 따라가보면 나중에 누른 스위치는 2칸 이상 떨어진 전구상태에 영향을 줄 수 없다. 즉, i번째 스위치는 i-2번째 이하 전구를 변화시키지 않는다.
i-1번째 전구상태를 기준으로 잡으면 i번째에서 누르는 스위치가 마지막 스위치라고 할 수 있다. 스위치를 한번씩 확인하기 때문에 전구상태를 최소한으로 변화시킨다고도 볼 수 있다. 이렇게 예외를 차단하는 기준을 찾는게 중요한 것 같다.
기준이 i-1번째이기 때문에 0번째 스위치는 누를 수도 있고, 안누를 수도 있으므로 2가지 경우를 나눠 최솟값을 구한다.

import sys

input = sys.stdin.readline

N = int(input())
cur = input().strip()
light = input().strip()

result_1 = 0
result_2 = 0

def switchNumber(n):
  if n == "0":
    return "1"
  else:
    return "0"

# 0번째 스위치를 누른 경우
zeroClick = switchNumber(cur[0]) + switchNumber(cur[1]) + cur[2:]
result_1 += 1
for i in range(1, N):
  if zeroClick[i-1] != light[i-1]:
    if i == N-1:
      zeroClick = zeroClick[:i-1] + switchNumber(zeroClick[i-1]) + switchNumber(zeroClick[i])
    else:
      zeroClick = zeroClick[:i-1] + switchNumber(zeroClick[i-1]) + switchNumber(zeroClick[i]) + switchNumber(zeroClick[i+1]) + zeroClick[i+2:]
    result_1 += 1

if zeroClick != light:
  result_1 = -1

# 0번째 스위치를 안누른 경우
for i in range(1, N):
  if cur[i-1] != light[i-1]:
    if i == N-1:
      cur = cur[:i-1] + switchNumber(cur[i-1]) + switchNumber(cur[i])
    else:
      cur = cur[:i-1] + switchNumber(cur[i-1]) + switchNumber(cur[i]) + switchNumber(cur[i+1]) + cur[i+2:]
    
    result_2 += 1   

if cur != light:
  result_2 = -1

if result_1 >= 0 and result_2 >= 0:
  print(min(result_1, result_2))
elif result_1 < 0 and result_2 >= 0:
  print(result_2)
elif result_1 >= 0 and result_2 < 0:
  print(result_1)
else:
  print(-1)