n 자리로 이진수를 표현할 때 연속한 1 이 나오는 경우를 제외한 가짓수를 구하는 것이 문제이다.

예를 들어 n 이 3 인 경우

• 0 0 0
• 0 0 1
• 0 1 0
• 0 1 1
• 1 0 0
• 1 0 1
• 1 1 0
• 1 1 1

입력

출력

입출력 예

입력

3

출력

5

보충 설명

• a1 = 2 , a2 = 3
• an = ai-1 + ai-2 ( n >= 3)

*처음에 이해가 안될 수 있습니다. 일단 피보나치 수열을 이용하여 문제를 푸시고 조금 더 공부한 후에 다시 한 번 생각해 보세요.