진수 정렬 (Easy)

면접 대비

시간 제한1초메모리 제한1024 MB

요약

길이 N인 이진수 S가 주어질 때, 모든 N자리 이진수를 1의 개수로 정렬하고 같으면 뒤집은 값 순으로 정렬했을 때 S의 위치를 0번부터 세어 구한다.

문제

한별이는 길이 $N$ 의 이진수를 모두 모은 뒤 특별한 방식으로 정렬하여 사용하려 한다.

정렬 기준은 다음과 같다.

예를 들어, $N$ 이 3일 때 이진수는 다음 순서로 정렬된다.

어느날 친구 선린이가 찾아와 길이가 $N$ 인 이진수 하나를 주며 몇 번째 위치에 있는지 알려달라고 했다. 하지만 한별이는 다른 일이 많아 아직 이진수들을 정렬하지 못했다. 한별이를 도와주자!

첫째 줄에 이진수의 길이 $N$ 이 주어진다.

둘째 줄에 길이 $N$ 의 이진수 $S$ 가 주어진다.

이진수는 0으로 시작할 수 있다.

주어진 이진수와 길이가 같은 모든 이진수를 정렬하였을 때, 주어진 이진수는 몇 번째 위치에 있는지 출력한다.

위치는 $0$ 번부터 시작한다.