더하기와 곱하기

$K$ 자리의 이진수로 표현된 음이 아닌 정수 $X$가 주어진다. $X$는 정확히 $K$ 자리로 표현되므로, 제일 앞자리가 $0$일 수도 있다.

예를 들어, $X$의 값이 십진수로 $5$이고 $K=5$인 경우, $X$를 $5$ 자리 이진수로 표현하면 $00101$이 된다.

이 수에 아래 두 가지 연산 중 하나를 골라서 수행하는 것을 $0$ 번 이상 할 수 있다.

• $X$에 $1$을 더하고, 그 결과를 $2^K$으로 나눈 나머지를 $X$에 저장한다.
• $X$에 $2$를 곱하고, 그 결과를 $2^K$으로 나눈 나머지를 $X$에 저장한다.

여기서, $2^K$는 $2$를 $K$ 번 곱한 것을 의미한다. 예를 들어, $2^3 = 2 \times 2 \times 2 = 8$이고, $2^4 = 16$이다.

두 연산을 원하는 순서로 진행하여 $X$를 $0$으로 만드는 것이 목표이다. 이때, 필요한 최소 연산의 횟수를 구하는 프로그램을 작성하시오.

입력 형식

첫 줄에 $X$의 이진수 표현의 자릿수 $K$가 주어진다. ($1 \leq K \leq 1\,000\,000$)

두 번째 줄에 $K$ 자리의 이진수로 표현된 수 $X$가 주어진다.

출력 형식

첫 줄에 두 연산을 원하는 순서로 $0$ 번 이상 수행하여 $X$를 $0$으로 만들 때 필요한 최소 연산의 수를 출력한다.

예제 1

8
01011101

6

예제 2

8
01001100

6

예제 3

10
0011111101

5

예제 설명

예제 1에서, 첫 번째 연산을 $3$ 번 수행하면 $X$는 $K$ 자리 이진수로 $01100000$이 된다. 이후 두 번째 연산을 $3$ 번 수행하면 $X$는 $0$이 된다. 이 경우가 최소 횟수의 연산을 수행하는 방법이다.

예제 2에서, 두 번째 연산을 $6$ 번 수행하는 것이 최소 횟수의 연산을 수행하는 방법이다.

예제 3에서, 첫 번째 연산을 $3$ 번 수행하고 두 번째 연산을 $2$ 번 수행하여 $X$를 $0$으로 만드는 것이 최소 횟수의 연산을 수행하는 방법이다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

해설