문제

다음 두 가지 규칙을 지키면서 이진수를 만들고자 한다. 가능한 서로 다른 이진수의 개수를 구하는 프로그램을 작성하시오.

규칙1) 길이는 n이다.

규칙2) 0이 연속으로 존재하면 안된다.

예를 들어 길이가 3이라면, 길이가 3인 이진수는 다음과 같이 000, 001, 010, 011, 100, 101, 110, 111 8가지이다. 이 중 0이 연속으로 사용된 3개를 제외한 010, 011, 101, 110, 111 의 5가지가 답이다.

입력

이진수의 길이를 나타내는 자연수
n
이 입력된다.

[입력값의 정의역]
1≤n≤20

입력 예시

3

출력

가능한 경우의 수를 출력한다.

출력 예시

5

문제 풀이

규칙을 찾기 위해 n = 1~4까지 직접 세봤다.
직접 하다보니 아래와 같은 규칙을 확인할 수 있었다.

case = 2 > 3 > 5 > 8 > 13 > 21 ...
case2 = +1 +2 +3 +5 +7 ...

이진수의 개수 = case[i]+case2[i]

이를 이용해 피보나치 수열로 문제를 풀긴 했는데,
2개를 합치는 과정이 조금 이상해서 시원찮다.

초기값이 설정되어야 하니, case = [2]를 주기는 했는데,
하나의 피보나치를 가지고 같이 이용할 수 있을 것 같은데 좋은 생각이 나질 않는다.
(마지막 도움으로 chatGPT 찬스 써봤는데 자꾸 이상한 답을 줘서 혼자 고민해봐야할 것 같다)

n = int(input())

def fibo(n):
    if n == 1:
        return []
    elif n == 2:
        return [1]

    fib = [1,2]
    for i in range(2,n):
        fib.append(fib[i-1]+fib[i-2])
    return fib

# 초기값 설정 ( n = 1 이면 무조건 답은 2 )
case = [2]
caseIndex = fibo(n)

if n > 2:
    for i in range(n):
        case.append(case[i]+caseIndex[i])
    print(case[n-1])
elif n == 1:
    print(case[0])
elif n == 2:
    print(case[0]+caseIndex[0])