백준 2138번 파이썬 문제풀이(전구와 스위치)

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

2138번: 전구와 스위치

---

웰노운 그리디 문제이다. 사실 처음에 생각하기가 참 쉽지 않았다...

 

해당 풀이방법은 다음과 같다.

 

1. 첫번째 스위치를 킬때와 끌때를 기준으로 나눈다.

 

2. 두번째 스위치부터 마지막까지 돌면서 각 자리 스위치를 킬지 말지를 결정해야하는데 방식은 다음과 같다. 현재 스위치자리 한칸 앞의 스위치와 정답 스위치의 해당 자리와 전구 상태가 같은지 비교해서 다르다면 해당 스위치를 무조건 키도록 하는 것이다. (왜냐하면 앞의 스위치는 해당자리를 벗어나면 바로 다음 스위치에서만 키거나 끌 수 있기 때문)

 

N = int(input())

before = list(map(int, input()))
after = list(map(int, input()))
temp_before = before[:]
cnt = 0
# 첫번째를 안눌렀을 때
for i in range(1, N):

    if before[i - 1] != after[i - 1]:
        cnt += 1
        before[i] = int(not before[i])
        before[i - 1] = int(not before[i - 1])
        if i != N - 1:
            before[i + 1] = int(not before[i + 1])
else:
    if ''.join(map(str, before)) == ''.join(map(str, after)):
        print(cnt)
        exit()

# 첫번째를 눌렀을 때
cnt = 1

temp_before[0] = not temp_before[0]
temp_before[1] = not temp_before[1]

for i in range(1, N):

    if temp_before[i - 1] != after[i - 1]:
        cnt += 1
        temp_before[i] = int(not temp_before[i])
        temp_before[i - 1] = int(not temp_before[i - 1])
        if i != N - 1:
            temp_before[i + 1] = int(not temp_before[i + 1])
else:
    if ''.join(map(str, temp_before)) == ''.join(map(str, after)):
        print(cnt)
        exit()

print(-1)