시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 45 21 19 45.238%

문제

2×N개의 전구가 두 줄로 놓여져 있다. 각 줄에는 N개의 전구가 있다. 각 전구는 상태는 켜져있거나 꺼져있다. 처음에 모든 전구는 꺼져있다.

현수는 일부 전구를 켜서 아름다운 패턴을 만드려고 한다. 현수는 행이나 열로 연속된 전구를 하나 이상 골라서 전구의 상태를 바꿀 수 있다. (꺼져있는 전구 -> 켬, 켜있는 전구 -> 끔)

현수가 만드려고 하는 패턴이 주어졌을 때, 최소 몇 번 만에 그 패턴을 만들 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 열의 크기 N이 주어진다. (1 ≤ N ≤ 10,000)

다음 두 줄에는 현수가 만드려고 하는 아름다운 패턴이 주어진다. 1은 전구가 켜져있는 상태이고, 0은 꺼져있는 상태이다. 

출력

현수가 최소 몇 번 만에 아름다운 패턴을 만들 수 있는지 출력한다.

예제 입력

20
11101101111000101010
01111101100000010100

예제 출력

7

힌트