[백준] 2138번 전구와 스위치 ★★★

💡문제접근

• 어떤 방법으로 최적의 해를 찾아야하는지 처음에 접근하기 어려워 접근법에 대해서 구글링을 해봤더니 정말 간단했다.
  1) 첫 번째 스위치를 누르는 경우와 누르지 않는 경우로 구분
  2) 이전 전구의 상태를 기준으로 스위치를 누를 것인지 아닌지 결정

💡코드(메모리 : 40808KB, 시간 : 180ms)

import copy
import sys
input = sys.stdin.readline

N = int(input())
before = list(map(int, input().strip()))
after = list(map(int, input().strip()))

non_press = 0
press = 1
def non_first_press():
    global non_press
    before_copy = copy.deepcopy(before)

    for i in range(1, N):
        if int(before_copy[i-1]) != int(after[i-1]):
            non_press += 1
            before_copy[i-1] = int(not before_copy[i-1])
            before_copy[i] = int(not before_copy[i])
            if i + 1 >= N:
                continue
            else:
                before_copy[i+1] = int(not before_copy[i+1])
    else:
        if ''.join(map(str, before_copy)) == ''.join(map(str, after)):
            print(non_press)
            sys.exit(0)

def first_press():
    global press
    before_copy = copy.deepcopy(before)
    before_copy[0] = int(not before_copy[0])
    before_copy[1] = int(not before_copy[1])

    for i in range(1, N):
        if int(before_copy[i-1]) != int(after[i-1]):
            press += 1
            before_copy[i-1] = int(not before_copy[i-1])
            before_copy[i] = int(not before_copy[i])
            if i + 1 >= N:
                continue
            else:
                before_copy[i+1] = int(not before_copy[i+1])
    else:
        if ''.join(map(str, before_copy)) == ''.join(map(str, after)):
            print(press)
            sys.exit(0)

non_first_press()
first_press()
print(-1)

💡소요시간 : 42m