가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 이 얇은 바닥을 1X2, 2X1, 2X2의 덮개를 이용해 채우려 한다.
바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오
이 문제를 접한 후 먼저 N = 1인 순간부터 경우의 수를 계산하여 확인해 본 결과
N = 1 -> 1가지
N = 2 -> 3가지
N = 3 -> 5가지
N = 4 -> 11가지
N = 5 -> 21가지
의 형태로 나오게 되었다.
처음에 이 값을 기초로 규칙성을 찾아보았으나 찾을 수 없었다.
그 이유는 점화식이 단항으로 구성될 것이라 생각했는데 이 문제는 가로 2 크기의 덮개 때문에 다항으로 점화식이 구성되었기 때문이라는 것을 문제를 다시 복기하면서 깨닫게 되었다.
이후 이 덮개의 최대 크기인 2를 기준으로 생각해 본 결과 덮개의 경우의 수는 n-1, n-2의 덮개의 경우의 수와 관련이 있다고 생각했다.
어디서 문제가 발생했나 생각해본 결과 2X2 덮개를 만드는 3가지 경우 중 2X1 덮개 2개를 사용하는 방법은 이미 n-1개의 덮개의 경우의 수에 포함되어 중복된다는 사실을 알게 되었고
최종적으로 An = A(n-1) + 2*(A(n-2))의 점화식을 사용해 문제를 해결하였다.
위의 점화식을 기반으로 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))