[Python] 11726번 2xn 타일링

오늘 풀어볼 문제는 2xn 타일링 시리즈 이다

2xn 사이즈의 직사각형을 1x2, 2x1사이즈의 타일로 채우는 경우의수를 구하는 문제이다

먼저 2x1 직사각형을 채우는 경우의 수는 몇개일까?

2x1 사이즈의 블럭 하나를 놓는 경우뿐이다

그렇다면 2x2 직사각형은?

1x2사이즈 두개, 2x1사이즈 두개 이렇게 2가지 경우가 있다

그다음으로 2x3은?

2x1사이즈에 2x2를 만드는 두가지 방법을 붙이거나

2x2로 만들어진 직사각형에 2x1을 붙이는 방법이 있다!

그렇다면 2xn의 직사각형을 만드는 경우의 수는

2x(n-2)직사각형에 2x2사이즈를 더해 만든경우와

2x(n-1)직사각형에 2x1사이즈를 더해 만든 경우 두개를 합하면 나오지 않을까?

nemo = {1:1,2:2}  # 2x1,2x2 사이즈를 만드는 경우의수

def nemo2(n):
  if (n in nemo):	#전에 계산한 적이 있다면 결과값 리턴
    return nemo[n]
  
  nemo[n] = nemo2(n-1) + nemo2(n-2)		#2x(n-2)에서 1x2 사이즈 블럭두개
  return nemo[n]						#2x(n-1)에서 2x1 사이즈 블럭하나


n = int(input())
print(nemo2(n) % 10007)

어? 그런데 2x(n-2)에서 블럭을 2x1두개랑 1x2두개를 붙이는 경우 두개아닌가요??

그 경우는 2x(n-1)에서 2x1사이즈 블럭하나 붙인 경우에 포함되어있다!

마치며

굳

해당 글은 직접 공부한 내용을 정리한 글입니다
어설픈 코딩실력은 너그럽게 봐주시고 조언은 항상 환영입니다..!