이진수
시간 제한2초메모리 제한128 MB
1을 0→10, 1→01 규칙으로 N번 확장한 이진 수열에서, 문자열을 직접 만들지 않고 연속된 0의 그룹 개수를 구하는 문제입니다.
문제
0과 1로 이루어진 이진수가 있다. 한 이진수에서 다음 이진수를 만들 때는 모든 문자를 동시에 바꾼다. 0은 10으로, 1은 01로 바꾼다. 첫 번째 이진수는 1이다. 처음 몇 개를 나열하면 다음과 같다.
1 -> 01 -> 1001 -> 01101001 -> ...
정수 N이 주어질 때, N번째 이진수에 들어 있는 연속된 0의 묶음 개수를 구하시오. N = 4이면 이진수는 01101001이고, 연속된 0의 묶음은 세 개이다.
입력
첫째 줄에 정수 N (1 <= N <= 1,000)이 주어진다.
출력
첫째 줄에 답을 출력한다.