[백준/Python]11726: 2 x n 타일링

문제

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

백준 문제집 - BOJ 길라잡이 베타 (1)

---

풀이

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

 

DP(동적 프로그래밍)로 분류되어있으니 점화식을 사용하는건 당연하고, 대강 체크해본결과 피보나치일거란 예감이 들었다.
일단 n = 1, 2, 3...일때를 가정하며 계산해보니 역시 피보나치 수열과 비슷한 결과가 나왔다.

n = 1일때 👉 1
n = 2일때 👉 2
n = 3일때 👉 3
n = 4일때 👉 5
...

 

기존의 피보나치 수열은 f(0) = 0, f(1) = 1를 베이스로 f(2) = 1, f(3) = 2...이므로 한칸씩 땡겨주기만 하면 된다.
즉 f(1) = 1, f(2) = 2...로 진행되는 셈이다.

 

전체 코드

# 메모리: 31120KB / 시간: 44ms
from sys import stdin


n = int(stdin.readline())
mod = 10007

def fibonacci(n):
    arr = [0] * (n+1)
    arr[1] = 1

    if n >= 2:
        arr[2] = 2
        for i in range(3, n+1):
            arr[i] = (arr[i-1] + arr[i-2]) % mod
    return arr[n]

print(fibonacci(n))

 

 

헌데 다른 풀이들을 보니 조합을 이용하는 방법도 있었다.
n개의 타일링을 할 때, 2 x 1 타일을 i개 사용하고 나머지를 1 x 2 타일로 채우는 경우의 수를 계산하는 방식이다.
2 x 1 타일을 i개 사용하면 남은 공간은 n - i * 2가 되는데, 이 공간을 모두 1 x 2 타일로 채우는것이다.

조합 공식을 사용해서 $ _nC_r = \frac{n!}{r!(n-r)!} $ 과 같이 계산하면 된다.

# 메모리: 33372KB / 시간: 68ms
from sys import stdin
from math import factorial


n = int(stdin.readline())
mod = 10007
ret = 0

for i in range(n//2 + 1):
    ret += factorial(n-i) // factorial(i) // factorial(n - i*2)

print(ret % mod)

 

피보나치를 사용하는편이 더 효율적이다.