t_바닥공사_223

문제

바닥을 덮개로 채워야한다. 가로 N, 세로 2이다.
덮개는 (1,2) , (2,1) , (2, 2) 의 크기를 가지고 있다.
바닥을 채우는 모든 경우의 수를 구하시오
(2,2) = (1,2) * 2 or (2,1) * 2

답

틀렸던 생각

2,2 로 다 채우고 나머지는 1,2 로 매꾼다
2,2 를 변형할 수 있는 다른 덮개로 바꾸는 경우를 샌다
==> 수학적으로 풀면 풀수 있을 듯하지만… 일단 못풀고 시험당일날 생각하기는 어려움

옳은 답
이미 다채워져 있고 나머지를 채운다는 식으로 접근을 한다
하나남았을땐 1,2 인 직사각형
2개 남았을 땐 1,2인거 두개 2,1인거 두개 2,2인거 하나 넣는 경우의수 3개가 존재한다.
하지만 1,2인가 두개인경우는 하나남았을때를 두번 반복한것과 겹친다.
고로 빼줘야한다.
Therefore , 1 남았을 경우 1개 {(1,2)} , 2개 남았을 경우 2개 {(2,1),(2,2)}
$A_i = A_{i-1} + A_{i-2} \times 2$
이런식으로 된다.

탑다운 형식

row = int(input.strip())

# <span id="a1-1-a2-3"></span>a1 = 1 a2 = 3

def search(i):
    if i == 1 :
        return 1 
    if i == 2 :
        return 3
    return search(i-1) + search(i-2)*2

print(search(row)%796796)

보텀업 형식

# <span id="앞서-계산된-결과를-저장하기-위한-dp-테이블-초기화-"></span>앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화 
n = int(input.strip())

d = [0] * 1001
 
d[1] = 1 
d[2] = 3 

for i in range(3, n + 1):
    d[i] = (d[i - 1] + 2 * d[i - 2]) % 796796

print(d[n])

수가 매우 커지면 탑다운 형식은 메모리 문제가 생기기 쉽다. 재귀는 깊이 제한이 있기 때무네