바닥 공사

문제

가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 이 얇은 바닥을 1X2, 2X1, 2X2의 덮개를 이용해 채우려 한다.
바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오

나의 풀이

1. 이 문제를 접한 후 먼저 N = 1인 순간부터 경우의 수를 계산하여 확인해 본 결과
   N = 1 -> 1가지
   N = 2 -> 3가지
   N = 3 -> 5가지
   N = 4 -> 11가지
   N = 5 -> 21가지
   의 형태로 나오게 되었다.
   처음에 이 값을 기초로 규칙성을 찾아보았으나 찾을 수 없었다.
   그 이유는 점화식이 단항으로 구성될 것이라 생각했는데 이 문제는 가로 2 크기의 덮개 때문에 다항으로 점화식이 구성되었기 때문이라는 것을 문제를 다시 복기하면서 깨닫게 되었다.

2. 이후 이 덮개의 최대 크기인 2를 기준으로 생각해 본 결과 덮개의 경우의 수는 n-1, n-2의 덮개의 경우의 수와 관련이 있다고 생각했다.

   • n-1개의 덮개의 경우의 수에 2X1 덮개를 더하는 경우
   • n-2개의 덮개의 경우의 수에 2X2 덮개를 만드는 경우 총 3가지를 더한 경우
   • 위의 두 경우를 합한 An = A(n-1) + 3*(A(n-2))의 점화식을 만들었으나 정답이 나오지 않았다.

3. 어디서 문제가 발생했나 생각해본 결과 2X2 덮개를 만드는 3가지 경우 중 2X1 덮개 2개를 사용하는 방법은 이미 n-1개의 덮개의 경우의 수에 포함되어 중복된다는 사실을 알게 되었고
   최종적으로 An = A(n-1) + 2*(A(n-2))의 점화식을 사용해 문제를 해결하였다.

4. 위의 점화식을 기반으로 bottom up 방식으로 반복문을 사용하여 dp문제를 구현하고 이후 top down 방식으로 재귀를 사용하여 풀어보았다.

코드

n = int(input())


def bottom_up(x):
    dp = [0] * (n + 1)

    dp[1] = 1
    dp[2] = 3
    dp[3] = 5

    for i in range(4, n + 1):
        dp[i] = (dp[i - 1] + 2 * dp[i - 2]) % 796796
    return dp[x]


def top_down(x):
    dp = [0] * (n + 1)

    dp[1] = 1
    dp[2] = 3
    dp[3] = 5

    if dp[x] != 0:
        return dp[x]

    dp[x] = top_down(x - 1) + (top_down(x - 2) * 2) % 796796
    return dp[x]


print(bottom_up(n))
print(top_down(n))