파이썬, 2xn 타일링 문제

 

2xn 타일링 문제

 

글. 오상문 sualchi@daum

2xn 영역을 2x1 또는 1x2 타일로 채우는 경우의 수를 구하는 문제입니다.
계산 방법은 피보나치 수열과 유사합니다.

 

n    경우의 수

------------

1:    1

2:    2

3:    3

4:    5

5:    8

...

 

 

# 처음부터 다시 계산하는 방식
def solution1(n):         
  answer = 0
  a = 2
  b = 3 
  if n < 4:

    return n  
  for i in range(4, n+1):
    answer = a+b
    a, b = b, answer          
  return answer

 

# 리스트를 이용한 재활용 방식  
dp = [0 for i in range(10001)]

 

def solution2(n):
  if n <= 2:        # dp[1]:1, dp[2]:2
    return n
  if dp[n] > 0:
    return dp[n]   
  dp[n] = solution2(n-1) + solution2(n-2)
  return dp[n]
#----------------------------

 

for n in range(1,21):
  print(n, ':', solution1(n), solution2(n))

 

[실행 결과]
1 : 1 1
2 : 2 2
3 : 3 3
4 : 5 5
5 : 8 8
6 : 13 13
7 : 21 21
8 : 34 34
9 : 55 55
10 : 89 89
11 : 144 144
12 : 233 233
13 : 377 377
14 : 610 610
15 : 987 987
16 : 1597 1597
17 : 2584 2584
18 : 4181 4181
19 : 6765 6765
20 : 10946 10946

 

<이상>