[백준] 11727 문제 in 파이썬

백준 11727 : 2 x n 타일링 2

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

문제

풀이

key

• 2 x n 타일링 1번에서와 마찬가지로 다이나믹 프로그래밍을 활용하는 문제였다.
  
  
  
  
• 위 그림처럼 2 x n 타일링에서 n 번째 경우의 수는 (n - 1 번째 모든 경우의 수에 1 _ 2 타일을 붙인 수) + (n - 2번째 모든 경우의 수에 2 _ 1 + 2 * 1 타일을 붙인 경우의 수)라는 점에서는 2 x n 타일링 1번과 다르지 않다.
• 이번에는 2 _ 2 타일이 붙는다는 조건이 추가 되었는데 사실 이건 2 _ 1 + 2 _ 1 타일을 붙였을 때의 경우의 수와 같다. 왜냐하면 결국 두 타일의 넓이는 2 _ 2로 똑같기 때문이다.
• 따라서 (n - 1 번째 모든 경우의 수에 1 _ 2 타일을 붙인 수) + 2 _ (n - 2번째 모든 경우의 수에 2 _ 1 + 2 _ 1 타일을 붙인 경우의 수)를 해주면 된다.

완성된 코드