[백준] 11726 문제 in 파이썬

백준 11726 : 2xn 타일링

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

문제

풀이

점화식 찾기

• 이 문제는 다이나믹 프로그래밍 기법을 활용하여 푸는 문제이다.
• 대부분의 문제와 같이 이 문제 또한 점화식을 사용하여 풀 수 있다.

규칙 찾기

• 위 그림과 같이 수열 An의 n이 1씩 증가할 때마다 가로 1 * 세로 2와 가로 2 * 세로 2 사각형에 각각 n-1항의 타일 모양과 n-2 항의 타일 모양이 오른쪽에 붙는 형태로 n 항의 타일 모양이 결정된다.
• 예를 들어 n = 4일 때의 경우 가로 1 * 세로 2 타일의 오른쪽에 n = 3일 때의 타일 모양이 그대로 붙어 3개, 가로 2 * 세로 2 타일의 오른쪽에 n = 2일 때의 타일 모양이 그대로 붙어 2개가 더해진다.
• 따라서 점화식을 구하면
  An = An-1 + An-2 (단, A >= 3일 때)가 된다.

완성된 코드