iktk   2년 전


문제

퍼즐을 좋아하는 Dyzio는 Jasiek의 친구입니다. Jasiek은 어느날 Dyzio로부터 수수께끼를 하나 받았습니다.

처음에 끈 하나가 주어진다. 이 끈을 규칙에 맞게 잘라야 한다. 끈을 자르는 방법은 0과 1만으로 구성된 문자열로 표현된다.

첫 문자가 1이라면 끈을 반으로 자르라는 의미이며, 0이라면 끈을 그대로 두고 작업을 종료한다는 뜻이다.

만약 끈을 반으로 잘랐을 경우, 왼쪽 절반을 자르는 규칙과 오른쪽 절반을 자르는 규칙이 동일한 형식으로 이어서 나타난다.

항상 왼쪽 끈에 대한 규칙이 먼저 나타난다.

규칙에 맞게 끈을 자를 때 가장 짧은 조각을 얻기 위해 끈을 잘라야 하는 최소 횟수를 구하자.

가위는 위험한 물건이기 때문에 Jasiek은 가위를 꺼내면 엄마에게 혼납니다.

그 대신 다행히도 Jasiek은 컴퓨터가 있어서 끈 자르는 시뮬레이션하는 프로그램을 작성할 수 있었습니다.

Jasiek이 작성한 프로그램을 여러분도 작성해 보시기 바랍니다.

입력

입력의 첫 번째 줄에는 정수 $n$($1\le n\le 20\,000$)이 포함됩니다.

입력의 두 번째 줄에는 길이가 $n$이고 사이에 공백이 없으며 0 또는 1로만 이루어진 문자열이 주어집니다.

이는 Dyzio가 Jasiek에게 준 끈을 자르는 규칙을 나타내는 문자열입니다.

출력

가장 짧은 끈 조각을 얻기 위해 끈을 잘라야 하는 최소 횟수를 정수로 출력합니다.

댓글을 작성하려면 로그인해야 합니다.