[BOJ 2138] 전구와 스위치

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

2138번: 전구와 스위치

원래 앞 2개 스위치 끄기 / 켜기, 뒤 2개 스위치 끄기 / 켜기를 고려해서 경우의 수를 4개로 풀었다가, jh05013님 코드를 확인한 후에 앞 스위치 2개를 끄기 / 켜기로 경우의 수를 2개로 줄였다.

 

풀이

어제 풀었던 행렬과 비슷한 문제이다.

스위치를 두 번 이상 누르는 것은 의미가 없으며, for문으로 돌리면 한 번 정해진 전구는 더 이상 바꿀 수 없다는 특징을 가지고 있다.

 

이렇게 하여 0번째 + 1번째 전구를 뒤집고 시작할 때 / 0번째 + 1번째 전구를 가만히 두고 시작할 때 2가지 경우로 나눌 수 있다.

이 이후에는 0번째 전구를 확인하여 정답 전구랑 다르면 0번째+1번째+2번쨰 전구를 뒤집어주고, 아니라면 가만히 둔다. 이러면 0번째 전구는 고정이 됐고, 더 이상 바꿀 수가 없다.

그 다음 1번째 전구를 확인하여 정답 전구랑 다르면 1번째 + 2번째 + 3번째 전구를 뒤집어주고, 아니라면 가만히 둔다.

이러면 1번째 전구는 고정이 됐고, 더 이상 바꿀 수가 없다.

이렇게 계속 반복하여 n-2번째 전구를 확인하여 정답 전구와 다르면 n-2번째 + n-1번째 전구를 뒤집어주고, 아니라면 가만히 둔다.

 

이렇게 하여 정답인 전구가 있는지 있으면 정답을 출력하고, 아니라면 -1을 출력해주면 된다.

 

코드

n = int(input())
a = [*map(int, input())]
b = [*map(int, input())]
s = a[:]
ans1 = 0
for i in range(n-1):
    if s[i] != b[i]:
        for j in range(i, i+3):
            if j < n: s[j] = 1 - s[j]
        ans1 += 1
flag1 = True if s == b else False
s = a[:]
s[0], s[1] = 1-s[0], 1-s[1]
ans2 = 1
for i in range(n-1):
    if s[i] != b[i]:
        for j in range(i, i+3):
            if j < n: s[j] = 1 - s[j]
        ans2 += 1
flag2 = True if s == b else False
 
print(min(ans1, ans2) if flag1 and flag2 else ans1 if flag1 else ans2 if flag2 else -1)