문제

2*1의 직사각형 블럭을 이용하여
크기의 직사각형 모양으로 채우려고 한다.

가능한 방법의 수를 구하여라.
직사각형 블럭은 무한정 있다고 가정한다.

입력

첫 줄에 n이 입력된다.

입력 예시

3

출력

2*n의 직사각형을 채울 수 있는 방법의 수를 출력하시오.

출력 예시

3

문제 풀이

피보나치 수열을 이용해서 풀면 된다.
처음에는 이해가 잘 안가서 찾아보다보니, 해당 문제에 규칙을 확인했고
그에 맞춰서 풀었다.

피보나치를 통해 합을 구했고, 해당 index의 값을 출력해주면 끝.

# 2*n 의 n 값 받기
n = int(input())

# 네모 상자를 채우는 공식 : T(i) = T(i-1) +T(i-2)
def fibo(n):
    cnt = 0
    if n == 1:
        cnt = 1
    elif n == 2:
        cnt = 2

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

print(fibo(n))