[백준] 2138번 전구와 스위치 (Python)

백준 2138 전구와 스위치

문제가 어렵진 않았지만 생각하지 못했던 부분이 있었다. 문제를 해결하는 포인트는 다음과 같았다.

1. 첫 번째 스위치는 눌러야 하는지 알 수 있는 방법이 없기 때문에, 첫 번째 스위치를 누르는 경우와 누르지 않는 경우 2가지로 나눠야 한다.
2. 오른쪽으로 하나씩 탐색한다면, 첫 번째 스위치를 제외하고 n 번째 스위치는 n - 1번째 전구를 바꿀 수 있는 유일한 방법이다. 즉, 그리디알고리즘을 활용해 해결할 수 있다.
3. 처음과 마지막은 전구가 2개씩만 바뀌지만, 입력값 앞뒤에 하나씩 임의의 값을 넣어준다면 예외 처리를 할 필요가 없다.
4. 정답을 확인할 때는 마지막 한 글자만 비교하면 된다.

문제를 해결하면서 이러한 부분을 쉽게 떠올렸지만, 내가 실수한 부분은, 첫 번째 버튼을 누르거나 누르지 않거나 둘 중 하나의 경우에만 답이 나올 수 있다고 생각했던 부분이다. 두 가지의 경우의 수를 모두 확인하고 최솟값을 출력하거나, 첫 번째 스위치를 누르지 않은 부분에서 답이 나왔을 때 exit을 해야 했다.

import sys
import copy

def switch(s, n):
    for i in range(3):
        if s[n - 1 + i] == "0":
            s[n - 1 + i] = "1"
        else:
            s[n - 1 + i] = "0"

sys.stdin.readline()
s1 = list("0" + sys.stdin.readline().strip() + "0")
s2 = copy.deepcopy(s1)
ans = list(sys.stdin.readline().strip())
res = 1e9

# 첫 번째 스위치 누른 경우
cnt = 1
ptr = 2
switch(s1, 1)
while(ptr < len(s1) - 1):
    if s1[ptr - 1] != ans[ptr - 2]:
        cnt += 1
        switch(s1, ptr)
    ptr += 1
if s1[-2] == ans[-1]:
    res = min(res, cnt)

# 첫 번째 스위치를 누르지 않은 경우
cnt = 0
ptr = 2
while(ptr < len(s2) - 1):
    if s2[ptr - 1] != ans[ptr - 2]:
        cnt += 1
        switch(s2, ptr)
    ptr += 1
if s2[-2] == ans[-1]:
    res = min(res, cnt)

print(res if res != 1e9 else -1)