[백준/Python] 11726번 2xn 타일링

알 수 없는 사용자 2022. 7. 17. 20:21

11726번: 2×n 타일링

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

www.acmicpc.net

n = int(input())
a_1 = 1
a_2 = 1
for _ in range(2, n+1):
    temp = (a_1 + a_2) % 10007
    a_1 = a_2
    a_2 = temp

print(a_2)

1. n = 1일 때 1, 2일 때 1가지 방법으로 배치 가능하다.

2. n = 3일 때는 위의 n=1일때 가로길이 2짜리 블록을 배치하는 방법 + n=1일 때 가로 1짜리 블록을 배치하는 방법이다.

3. 따라서 점화식은 a_n = a_(n-1) + a_(n-2) (n>=3)이다.

4. 문제의 10007로 나눈 나머지 출력 조건을 만족하며 점화식을 코드로 표현하면 다음과 같다.