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

 

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

11726번: 2×n 타일링

문제분석

코드

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로 나눈 나머지 출력 조건을 만족하며 점화식을 코드로 표현하면 다음과 같다.