전구
시간 제한1초메모리 제한128 MB
2×N 격자의 목표 패턴이 주어질 때, 행 또는 열의 연속 구간을 토글하는 연산으로 그 패턴을 만드는 최소 연산 횟수를 구합니다.
문제
2×N개의 전구가 두 줄에 놓여 있다. 각 줄에는 N개의 전구가 있으며, 처음에는 모든 전구가 꺼져 있다.
현수는 몇 번의 조작으로 원하는 아름다운 패턴을 만들려고 한다. 한 번의 조작에서는 한 행 또는 한 열에서 서로 이어진 전구를 하나 이상 고른 뒤, 고른 전구의 상태를 모두 반대로 바꾼다. 꺼진 전구는 켜지고, 켜진 전구는 꺼진다.
목표 패턴이 주어졌을 때, 그 패턴을 만들기 위해 필요한 최소 조작 횟수를 구하시오.
입력
첫째 줄에 열의 개수 N이 주어진다. (1 ≤ N ≤ 10,000)
다음 두 줄에는 현수가 만들려고 하는 패턴이 주어진다. 1은 전구가 켜진 상태를, 0은 전구가 꺼진 상태를 의미한다.
출력
현수가 원하는 패턴을 만들기 위해 필요한 최소 조작 횟수를 출력한다.