풀이

그리디 알고리즘이라 하면 가장 큰 것부터, 가장 작은 것부터 이런 식으로 단순하게 생각했다. 그러나 난이도가 올라갈 수록 최적의 해를 찾는 것 또한 그리디의 일부라는 것을 알게 되었다. 이 문제에서 바꿔줄지 말지를 결정하는 것이 최적의 해고 , 또한 경우의 수도 생각해야했다. 바꿀지 말지를 결정하는 것은 본인의 순서가 아닌 본인 - 1 순서를 보고 정하는데 첫번째 전구는 그게 없기 때문에, 첫번째 전구를 바꿔주는 경우와 안바꿔주는 경우를 모두 생각해주어야해서 까다롭다.```
import sys
input = sys.stdin.readline

n = int(input())
A = list(map(int, input().rstrip()))
B = list(map(int, input().rstrip()))

def change(A, B):
copy_A = A[:]
press = 0
for i in range(1,n):
if copy_A[i-1] == B[i-1]:
continue
press += 1
for j in range(i-1, i+2):
if j < n:
copy_A[j] = 1 - copy_A[j]

if copy_A == B:
    return press
else:return int(1e9)

res = change(A,B)
A[0] = 1-A[0]
A[1] = 1-A[1]

res = min(res, change(A,B)+1)

if res == int(1e9):
print(-1)
else:print(res)