17359번 - 전구 길만 걷자

선린 친구들은 ✨인기스타 슈퍼인싸 예원쌤✨을 존경한다. 방학 동안 선생님을 뵐 수 없다니! 그래서 학생들은 방학식 날 💡전구 길만 걷자💡라는 엄청난 이벤트를 준비했다.

💡💡💡💡👨‍🏫💡💡💡💡

아무도 몰랐지만, 사실 선린의 과학실에는 전구가 일렬로 이어진 전구 묶음이 N개 있다. 학생들은 이 묶음을 일렬로 이어 전구 길을 만들기로 했다. 하지만 묶음에는 불이 들어오지 않는 전구가 섞여 있었는데, 전구들을 일렬로 이어 놓으니 켜진 전구와 꺼진 전구가 번갈아 나타나서 전구 길이 예쁘지 않았다.

그래서 학생들은 전구 길이 최대한 예쁘도록 묶음을 배열하려고 한다. 전구 길은 전구 상태가 바뀌는 횟수가 최소일 때 가장 예쁘다고 한다. 이는 켜진 전구를 1, 꺼진 전구를 0이라 했을 때, 전구 길에 01 또는 10이 최소로 나타나야 한다는 의미이다.

예를 들어, (1011) 묶음과 (1000) 묶음을 이어 붙여야 한다고 하자. 이때는 (10111000) 순서로 잇는 것이 (10001011) 순서로 잇는 것보다 예쁘다. 전자는 전구의 상태가 3번 바뀌고, 후자는 전구의 상태가 4번 바뀌기 때문이다.

그런데 갑자기 세한이가 코드를 작성해서 이를 계산하자고 한다.

세한이와 함께 전구 길을 예쁘게 꾸며보자!

첫째 줄에 전구 묶음의 개수 N이 주어진다. (1 ≤ N ≤ 10)

둘째 줄부터 N개의 줄에 걸쳐, 각 줄마다 전구 묶음의 상태를 나타내는 문자열이 주어진다. 문자열은 0 또는 1로만 이루어져 있으며 0은 꺼진 전구를, 1은 켜진 전구를 의미한다.

문자열의 길이는 1 이상 100 이하이다.

전구 묶음을 가장 예쁘게 배치했을 때, 전구의 상태가 바뀌는 횟수를 출력한다.