시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB180590869849.680%

문제

방탈출 게임을 하던 혜민이는 마지막 문제에 봉착했다. 단서는 다음과 같다.

  1. 앞에는 일렬로 놓여진 N개의 버튼이 모두 불이 꺼진 상태로 있다.
  2. 0 또는 1로 구성되어 있는 N자리 수가 적힌 쪽지가 있다.
  3. 0은 불이 꺼진 버튼, 1은 불이 켜진 버튼을 뜻한다.
  4. 불이 켜져 있는 버튼을 누르면 불이 꺼지고, 불이 꺼져 있는 버튼을 누르면 불이 켜진다.
  5. 버튼을 누르면 그 버튼 뿐만이 아닌 오른쪽 두 개의 버튼도 같이 눌린다. 

혜민이는 현재 모두 불이 꺼진 상태에서 버튼을 최소로 눌러서 쪽지와 똑같은 상태로 만들어야 한다는 것을 알아냈다! 혜민이를 도와줘서 방탈출 게임에 성공하자.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000,000)가 주어지고 둘째 줄에는 쪽지에 적혀 있는 N자리의 수가 빈 칸을 사이에 두고 주어진다.

출력

눌러야하는 버튼의 최솟값을 출력한다.

예제 입력 1

7
0 0 1 0 0 1 0

예제 출력 1

2

힌트

다음과 같이 2개의 버튼을 눌러 쪽지에 적혀 있는 상태를 만들 수 있다.   

  • 모든 버튼이 꺼진 처음 상태 → 0 0 0 0 0 0 0
  • 세 번째 버튼을 누른 상태 → 0 0 1 1 1 0 0
  • 네 번째 버튼을 누른 상태 → 0 0 1 0 0 1 0

출처

University > 한양대학교 ERICA 캠퍼스 > 2018 HEPC > MAVEN 5번