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

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

규칙을 먼저 찾아보자

본인은 A4용지에 그려가며 규칙을 찾아보았다.

즉, 전에 풀었던 내용과 같은 방식이다.

https://koreatstm.tistory.com/148

[백준/Python] 2748:피보나치 수 2

이처럼 f(n) = f(n-1) + f(n-2)의 규칙이다.

이제 푸는것은 저번 블로그와 똑같다

 

타뷸레이션

n=int(input())

cache = [0] * 1001

for i in range(1,1001):

    if i==1:
        cache[i]=1
    elif i==2:
        cache[i]= 2
    else:
        cache[i]= cache[i-1] + cache[i-2]

print(cache[n]%10007)

 

메모이제이션

n=int(input())

cache=[0] * 1001

def func(n):
    if cache[n]:
        return cache[n]
    if n==1:
        cache[n]= 1
    elif n==2:
        cache[n]= 2
    else:
        cache[n] = func(n-1) + func(n-2)
    return cache[n]
print(func(n)%10007)