메모리 비트 전극 연산

면접 대비

시간 제한1초메모리 제한128 MB

요약

시작 문자열과 목표 문자열이 주어질 때 접두사나 접미사를 뒤집어 시작 문자열을 목표 문자열로 바꾸는 최소 연산 횟수를 구합니다.

문제

파벨은 컴퓨터 시스템 구조 수업에서 빠른 비트 연산을 지원하는 새로운 주기억장치 모델을 만들었다. 이 모델에서 메모리는 하나의 이진 문자열, 즉 0과 1이 나열된 하나의 열로 표현된다.

메모리 내용은 특수한 전극으로 바꾼다. 전극은 먼저 하나의 비트와 방향(왼쪽 또는 오른쪽)을 고른다. 그런 다음 고른 비트에서 시작해 그 방향으로 메모리의 끝(오른쪽) 또는 처음(왼쪽)에 도달할 때까지 지나는 모든 비트의 값을 반전시킨다.

예를 들어 메모리가 0010일 때 두 번째 비트와 오른쪽 방향을 고르면, 두 번째 비트부터 마지막 비트까지가 모두 반전되어 0101이 된다. 두 번째 비트는 0에서 1로, 세 번째 비트는 1에서 0으로, 네 번째 비트는 0에서 1로 바뀐다.

시작 메모리 내용과 목표 메모리 내용이 주어질 때, 시작 내용을 목표 내용으로 바꾸는 데 필요한 최소 연산 횟수를 구하여라.

첫째 줄에 정수 $n$ $(1 \le n \le 10^6)$ 이 주어진다.

둘째 줄에 길이 $n$ 의 이진 문자열이 주어진다. 이는 시작 메모리 내용이다.

셋째 줄에 길이 $n$ 의 이진 문자열이 주어진다. 이는 목표 메모리 내용이다.

시작 메모리 내용을 목표 메모리 내용으로 바꾸는 데 필요한 최소 연산 횟수를 한 줄에 출력한다.

다음은 10010000을 4번의 연산만에 00100111로 바꾸는 예이다. 각 줄 괄호 안의 구간은 그 연산으로 반전된 비트 구간을 나타낸다.