전구와 스위치
면접 대비시간 제한2초메모리 제한128 MB
현재 전구 상태와 목표 상태가 주어질 때, 이웃한 전구를 뒤집는 스위치를 최소 몇 번 눌러야 목표에 도달하는지 구하거나 불가능하면 -1을 출력합니다.
문제
N개의 스위치와 N개의 전구가 한 줄로 있다. 각 전구는 켜짐 또는 꺼짐 상태이다.
2번부터 N - 1번까지의 스위치 i를 누르면 i - 1번, i번, i + 1번 전구의 상태가 모두 바뀐다. 켜진 전구는 꺼지고, 꺼진 전구는 켜진다. 1번 스위치를 누르면 1번과 2번 전구가 바뀌고, N번 스위치를 누르면 N - 1번과 N번 전구가 바뀐다.
현재 전구 상태와 만들고 싶은 전구 상태가 주어진다. 목표 상태를 만들기 위해 스위치를 눌러야 하는 최소 횟수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정수 N (2 <= N <= 100,000)이 주어진다.
둘째 줄에는 현재 전구 상태를 나타내는 길이 N의 문자열이 주어진다. 셋째 줄에는 목표 전구 상태를 나타내는 길이 N의 문자열이 주어진다. 각 문자열에서 0은 켜짐, 1은 꺼짐을 뜻한다.
출력
스위치를 누르는 최소 횟수를 출력한다. 목표 상태를 만들 수 없으면 -1을 출력한다.