2×n 타일링

Algorithm/Python

[파이썬/백준 11726]2×n 타일링

문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 접근 그림을 보면 위와 같은 규칙을 찾을 수 있다. 피보나치 수를 구해주면 된다. 예전에 피보나치 수를 구하는 문제에서 정직하게 재귀를 사용했다가 시간초과가 나오고, 배열에 저장해도 시간초과가 나왔던 기억이 있다. 그래서 변수만 사용해서 답을 구했다. 코드 n = int(input()) if n < 3: print(n%10007) else: a, b = 1, 2 for _ in range(n-2): a, b = b, a+b print(b%10007)

박한결
'2×n 타일링' 태그의 글 목록