[백준 11726] 2×n 타일링

문제 

11726번: 2×n 타일링 (acmicpc.net)

11726번: 2×n 타일링

---

아이디어

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 f(n)이라고 하면 이를 점화식으로 표현할 수 있다. 

f(1) = 1, f(2) = 2이다. n이 3 이상인 경우 f(n) = f(n-1) + f(n-2)로 표현할 수 있다. 

 

f(4) = f(3) + f(2) = {f(2) + f(1)} + f(2) 와 같은 방식으로 계산이 진행되기 때문에 recursive call을 이용하면 메모리가 낭비될 수 있다. 따라서 점화식을 이용한 풀이를 위해 Dynamic programming 을 사용하였다. 

 

각각의 n에 대해 f(n)을 한 번만 저장해두면 매번 계산할 필요 없이 저장된 값을 이용할 수 있다.

---

Solution

n = int(input())

cache = [0 for _ in range(1001)]

cache[1] = 1 
cache[2] = 2 
for idx in range(3, 1001) : 
    cache[idx] = cache[idx-1] + cache[idx-2]
    
print(cache[n] % 10007)