천문대의 구역 분할 기록

문제

천문대는 일렬로 나열된 N개의 관측 칸을 조사한다. 각 칸에는 조사할 별이 하나 있거나 없으며, 처음에는 모든 칸을 하나의 구역으로 묶는다. 관측 프로그램은 구역을 재귀적으로 검사하면서 검사 기록을 남긴다. 이때 별이 있는 칸의 위치는 검사 도중 바뀌지 않는다. 어떤 구역을 검사하면 가장 먼저 그 구역에 대한 기록을 정확히 하나 남긴다. 그 구역에 있는 별의 수가 0개 또는 1개라면 추가 작업 없이 해당 구역의 검사를 끝낸다. 별이 2개 이상이면 구역을 연속한 두 구역으로 나눈다. 원래 구역의 칸 수가 L개일 때 왼쪽 구역에는 앞에서부터 ⌊L/2⌋개의 칸을 넣고, 오른쪽 구역에는 나머지 칸을 넣는다. 여기서 ⌊L/2⌋는 L을 2로 나눈 몫이다. 나눈 뒤에는 왼쪽 구역과 오른쪽 구역을 차례로 같은 규칙에 따라 검사한다. 분할하기 전에 남긴 원래 구역의 기록도 전체 기록 수에 포함한다. 분할하여 만들어진 구역에 별이 없더라도 그 구역의 검사를 시작할 때 기록을 하나 남긴다. 반면 별이 하나 이하인 구역은 칸이 여러 개여도 더 나누지 않는다. 따라서 같은 수의 별이 있더라도 별의 배치에 따라 전체 기록 수가 달라질 수 있다. 프로그램은 전체 N개 칸으로 이루어진 구역의 검사부터 시작한다. 모든 재귀 검사가 끝났을 때 남아 있는 기록의 총개수를 구해야 한다. 별이 전혀 없는 관측 칸 배열에서도 최초 구역의 검사는 수행한다. 각 기록은 서로 다른 검사 호출에 대응하며, 기록을 남긴 순서는 출력하지 않는다.

입력

첫째 줄에 칸 수를 나타내는 정수 N이 주어진다. 1 ≤ N ≤ 65,536이다.
둘째 줄에 길이가 정확히 N인 문자열 S가 주어진다. S는 문자 0과 1로만 이루어지며, 왼쪽부터 각 칸에 별이 없으면 0, 별이 있으면 1이다.

출력

모든 검사가 끝났을 때 남긴 기록의 총개수를 정수 하나로 출력한다.

8
10100001

5

5
00000

1

3
111

5

출처: Devin.KR 자체 제작