[백준 알고리즘] 11726번: 2xn 타일링 (Python)

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

11726번: 2×n 타일링

 

소스코드

 

 

풀이

★ 2 x n 직사각형을 1 x 2, 2 x 1 타일로 채울 수 있는 방법의 수는 2 x (n-1)을 채울 수 있는 방법의 개수 + 2 x (n-2)를 채울 수 있는 방법의 개수입니다 !

 

★ 점화식을 세우기 위해선 패턴을 파악해야 합니다.  n이 1부터 5일때까지를 대입해보면

 

n = 1, 방법: 1가지

 

n = 2, 방법: 2가지

 

n = 3, 방법: 3가지 (n이 1일 때 + n이 2일 때)

 

n = 4, 방법: 5가지 (n이 2일 때 + n이 3일 때)

 

n = 5, 방법: 8가지 (n이 3일 때 + n이 4일 때)

 

위와 같은 패턴을 점화식으로 만들어주면 됩니다 !

 

★ 결과값을 출력할 때 방법의 수를 10,007로 나눈 나머지를 출력해야 하는 것을 주의해야 합니다 :)