문제

N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 있는 전구는 켜지고, 켜져 있는 전구는 꺼지게 된다. 1번 스위치를 눌렀을 경우에는 1, 2번 전구의 상태가 바뀌고, N번 스위치를 눌렀을 경우에는 N-1, N번 전구의 상태가 바뀐다.

N개의 전구들의 현재 상태와 우리가 만들고자 하는 상태가 주어졌을 때, 그 상태를 만들기 위해 스위치를 최소 몇 번 누르면 되는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 전구들의 현재 상태를 나타내는 숫자 N개가 공백 없이 주어진다. 그 다음 줄에는 우리가 만들고자 하는 전구들의 상태를 나타내는 숫자 N개가 공백 없이 주어진다. 0은 켜져 있는 상태, 1은 꺼져 있는 상태를 의미한다.

출력

첫째 줄에 답을 출력한다. 불가능한 경우에는 -1을 출력한다.

예제 입력

3
000
010

예제 출력

3

풀이

n = int(input())

now = list(map(int, input()))
want = list(map(int, input()))

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

    if tmp == B:
        return cnt
    else:
        return 1e9

res = change(now, want)

now[0] = 1-now[0]
now[1] = 1-now[1]

res = min(res, change(now, want)+1)
if res!=1e9:
    print(res)
else:
    print(-1)

그리디 알고리즘으로 분류되는 문제다.

그리디 알고리즘;

탐욕 알고리즘이라고도 한다. 현재 상황에서 가장 최적인, 가장 좋은 결과를 선택하는 알고리즘이다.
최종적으로 나온 결과가 가장 최적이라 보장할 수 없다.
거스름돈 문제가 대표적인 예시.

1. 첫번째 전구를 눌렀을 때
2. 안눌렀을 때
이 두 가지 상황을 두고 문제를 풀면 된다.

첫번째 전구를 누르면 두번째 전구만 영향을 받지만, 나머지 전구들은 양 옆의 전구가 영향을 받기 때문에 첫번째 전구를 눌렀냐 아니냐에 따라 다른 전구들의 결과가 바뀌기 때문에 두 가지 상황을 고려해서 둘 중 어느 방법이 더 최적인지(버튼을 적게 누르는지) 도출해낸다.

후기

생각보다 꽤 어려웠다. 역시 골드는 골드인 거 같다!
다른 분들 풀이를 많이 참고하면서 공부했는데 도움을 많이 받았다. 특히, 불가능한 경우에 -1을 출력하라 해서 tmp가 B랑 같지 않으면 -1로 설정하고 조건을 추가해서 풀었더니 틀리더라. 그래서 참고한게 1e9(10억) 사용하기다. 제한사항이 10억 미만일 때 사용하는 무한 값이라고 한다. 자바에서는 사용한 적 없었는데 파이썬에서만 사용하는 듯하다.