2xn 타일링 문제, 타일이 두칸짜리만 있는 경우

2xn 타일링 문제, 타일이 두칸짜리만 있는 경우

 

글. 수알치 오상문 

 

2xn 타일링은 두칸 짜리가 n개 늘어선 구조입니다. 가장 간단한 문제는 타일이 두칸 짜리 한종류만 있는 경우입니다(가로/세로 배치 가능).

 

ooooooooo

ooooooooo

1234567....n

 

n이 1일 때: 가능한 경우는 1가지

n이 2일 때: 가능한 경우는 2가지 

n이 3일 때: 가능한 경우는 3가지 

n이 4일 때: 가능한 경우는 5가지 

n이 5일 때: 가능한 경우는 8가지 

n이 6일 때: 가능한 경우는 13가지 

...

 

경우의 수열에서 눈치챘겠지만 피보나치 수열과 유사합니다.

즉, 현재 n은 n-1과 n-2 경우를 합한 값입니다.  

 

초기값은 n이 1일 때 1, n이 2일 때 2입니다.

 

n   값

-------

1 :  1

2 :  2

 

점화식은 다음과 같습니다.

D[n] = D[n-1] + D[n-2] 

 

다음 파이썬 예제는 이 문제를 동적 프로그래밍과 반복문 두 가지 방식으로 풀고 있습니다.

(참조: 백준 11726  2xn 타일링 문제  https://www.acmicpc.net/problem/11726)

 

dp = [0,1,2] + [-1]*1000
def solution1(n):  # DP 이용, 초기값 2개  
    if n==1: return 1
    if n==2: return 2
    for i in range(3, n+1):
        dp[i] = (dp[i-1] + dp[i-2])%10007
    return dp[n]

def solution2(n): # DP 아님, 속도 빠름. 
    a, b = 1, 2
    if n==1: return 1
    if n==2: return 2
    for i in range(3, n+1):
        a, b = b, (a+b)%10007
    return b    

N = int(input())
print(solution1(N))
print(solution2(N))

 

<이상>