[백준/파이썬] 11726번

📍백준 11726번 문제

https://www.acmicpc.net/problem/11726

코드

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10**3)


def tile(n):
    res = [1, 1]
    for i in range(2, n+1):
        res.append(res[i-1]+res[i-2])
    print(res[-1] % 10007)


n = int(input())
tile(n)

풀이

가로 타일은 꼭 2개씩 세트로 배치해야하므로 2의 배수만 가능하다.

n	가로 타일 개수	세로 타일 개수	경우의 수
1	1	0	1
2	2	0	1
	0	2	1
3	2	1	2
	0	3	1
4	4	0	1
	2	2	3
	0	4	1

n = 1 일때는 1, n = 2일때는 2, n = 3일때는 3(1+2), n = 4일때는 5(2+3)
즉, 피보나치 수열이 완성된다.