방탈출

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

요약

버튼을 누르면 자기 자신과 오른쪽 두 버튼의 상태가 뒤집힐 때, 모두 꺼진 N개의 전구를 목표 0/1 상태로 만드는 최소 누름 횟수를 구한다.

문제

방탈출 게임을 하던 혜민이가 마지막 문제를 만났다. 단서는 다음과 같다.

눈앞에 버튼 N개가 일렬로 놓여 있고, 처음에는 모두 불이 꺼져 있다.
0과 1로만 이루어진 N자리 수가 적힌 쪽지가 있다.
0은 불이 꺼진 버튼, 1은 불이 켜진 버튼을 뜻한다.
불이 켜진 버튼을 누르면 불이 꺼지고, 불이 꺼진 버튼을 누르면 불이 켜진다.
버튼을 누르면 그 버튼뿐 아니라 오른쪽으로 이웃한 버튼 두 개도 함께 눌린다. 오른쪽에 남은 버튼이 두 개보다 적으면 실제로 있는 버튼만 눌린다.

모두 꺼진 상태에서 시작해 버튼을 최소 횟수로 눌러서 쪽지와 똑같은 상태를 만들어야 한다. 혜민이를 도와 방탈출에 성공하자.

첫째 줄에 N이 주어진다. ( $1 \le N \le 1{,}000{,}000$ )

둘째 줄에 쪽지에 적힌 N자리 수가 한 자리씩 공백으로 구분되어 주어진다.

쪽지와 똑같은 상태를 만들기 위해 눌러야 하는 버튼의 최소 횟수를 출력한다.

$N = 7$ 이고 쪽지에 적힌 수가 0 0 1 0 0 1 0이면 버튼을 두 번 눌러서 만들 수 있다.