시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB153461246540.190%

문제

0과 1로 구성된 이진수가 있다. 이 이진수에서 0을 10으로, 1을 01로 동시에 치환하면 길이가 두 배인 이진수를 얻을 수 있다. 이러한 이진수들을 차례로 나열하면 하나의 이진수 수열이 된다. 편의상 시작 수는 1이라고 하자. 처음 몇 개의 이진수들을 구해 보면,

1 → 01 → 1001 → 01101001 → …

이 된다.

N이 주어졌을 때, N번째 이진수에서 연속된 0들의 그룹이 몇 개나 있는지 알아내는 프로그램을 작성하시오. N=4일 경우의 이진수는 01101001이고, 따라서 이 안에는 연속된 0들이 세 그룹 있게 된다.

입력

첫째 줄에 정수 N(1 ≤ N ≤ 1,000)이 주어진다.

출력

첫째 줄에 답을 출력한다.

예제 입력 1

3

예제 출력 1

1

예제 입력 2

2

예제 출력 2

1

출처