[백준/python] 11726 2xn 타일링

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

11726번: 2×n 타일링

문제

 

코드

from functools import reduce

def in_cache(func): # decorator를 사용 - 메모이제이션

    cache = {}

    def wrapper(n):

        if n in cache:

            return cache[n]

        else:

            cache[n] = func(n)

            return cache[n]

    return wrapper

@in_cache

def factorial_reduce(n): # reduce 함수를 이용한 팩토리얼 함수

    if n==0: return 1

    return reduce(lambda x, y: x * y, range(1, n+1))

n = int(input())

two = n//2

ans = 0

for i in range(two+1):

    one = n - 2*i

    ans += factorial_reduce(i+one)//(factorial_reduce(i)*factorial_reduce(one))

   

print(ans%10007)

풀이

어떤 모양으로 할지는 블럭을 세로로 둘지 가로로 둘지에 결정된다. 따라서 입력받은 n을 1칸 또는 2칸으로 잘 나눠갖는 경우의 수를 세어보면 된다. 팩토리얼을 사용해야하는데 같은 수를 여러번 계산할 수 있으니 캐시를 이용하자.

처음엔 팩토리얼 내장 함수가 있을 것 같아 찾아봤는데, 아래와 같은 블로그를 발견했다. 내장함수인 reduce를 이용하여 람다 함수를 만드는 코드가 새롭고 써보고 싶어서 가져왔다. 또, 캐시를 데코레이터를 이용하여 코드를 분리하는 것도 시도해보고 싶어서 가져왔다.

이제 블럭 1개 또는 2개의 개수를 달리하여 계산한다. 같은 종류가 존재할 때의 순열 공식을 사용했다.

다 쓰고 돌려보니 196ms 시간이 걸렸다. 다른 분들의 코드를 보니 오히려 한번에 모든 팩토리얼을 계산하고 (1000밖에 없으므로...!) 바로 가져다 쓰는 편이 훨씬 빨랐다. 아니면 그냥 1부터 시작해서 아예 dp로 푸는 것이 나은 듯

 

참고

https://shoark7.github.io/programming/algorithm/several-ways-to-solve-factorial-in-python