🔴 문제 개요
🚀 난이도 : GOLD 4
문제는 심플합니다.
2×N 크기의 벽을 2×1, 1×2, 1×1 크기의 타일로 채우는 경우의 수를 구해보자.
제한 조건
- 첫째 줄에 N(1 ≤ N ≤ 1,000,000)이 주어진다.
- 첫째 줄에 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다.
풀이 개요
DP 방법론을 활용하는 전형적인 타일링 문제입니다. 이 문제는 다른 타일링 문제에 비해서도 시간 제한과 메모리 제한이 빡빡해서(Python 3 기준) 점화식을 최적화해야 풀이가 가능합니다.
🟠 Solution
아래의 3개의 블럭으로 위 2xn 블럭을 채우는 경우의 수를 구해야합니다. 이런 타일링 문제에서는 2xN에서 각 N의 경우마다 가지는 고유의 블록 수를 잘 활용하는 것이 가장 중요합니다.
먼저 N이 1인 경우, N이 2인 경우를 살펴보겠습니다. 이 경우들을 f(1), f(2)로 표기하겠습니다.
- f(1)은 명백하게
2x1 블록 하나와 1x1 블록 두개로 조합하는 두 가지경우의 수가 나올 수 있습니다. - f(2)는
f(1)에 f(1)을 덧붙이는 경우(2 x 2 = 4)와f(2)만이 가질 수 있는 고유한 경우의 수(3)의 7개의 경우의 수가 나옵니다.
f(3)부터는 DP 방법론과 중복을 고려해서 생각해야 경우의 수를 도출해볼 수 있습니다.
- 우선, f(2)에 f(1)을 덧붙이는 경우를 모두 고려할 수 있습니다. 이 경우 7x2의 14가지 경우의 수가 발생합니다.
- 다음으로 f(1)에 f(2)를 덧붙이는 경우를 고려할 수 있습니다. 다만, 이 경우의 수 중에서 f(2)가 f(1)의 조합으로 이루어진 경우는 바로 위에서 고려했으므로 제외해야합니다.
- 즉,
f(2)만이 가질 수 있는 고유한 경우의 수중f(1) 블록을 덧붙이는 경우의 수만 추가로 고려해주어야 합니다. - 그러면 3x2의 총 6가지 경우를 추가로 고려할 수 있습니다.
- 혹시 이 개념이 와닿지 않는 분은 타일링 문제의 기본 문제 격인 2xn 타일링을 참고해보시면 이해가 쉬우실 것 같습니다.
지금까지 이전 경우의 수 들로 f(3)을 조합하는 경우의 수에 대해서 고려했으니, 이제는 f(3)이 가지는 고유의 경우의 수를 생각해보아야 합니다.
- 아래 두 경우의 수가 만들어질 수 있습니다.
정리해보면, f(n)경우의 수가 가질 수 있는 고유의 경우의 수를 f'(n)이라고 한다면,
이제 점화식의 대략적인 형태를 유추해볼 수 있을 것 같습니다. f(n)을 만들기 위한 조합을 고려하는 건 알겠는데, 각 n이 가지는 고유의 경우의 수는 어떻게 알아낼 수 있을까요?
f'(3)의 형태를 보면 n이 홀수일 때 고유의 경우의 수를 유추해볼 수 있습니다.
단순히 가운데에 2x1 블록이 하나씩 추가된 경우에 해당되는데, 조금만 생각해보면 이러한 형태 말고는 다른 경우의 수는 나오지 않습니다. 2x1블록 외에 1x1이나 1x2 블록을 놓는다면 바로 횡으로 갈라지게 될테니까요. 즉, n이 홀수일 때, 고유한 경우의 수는 2입니다.
n이 짝수일 때도 다르지 않습니다.
같은 원리로 짝수일 때의 고유의 경우의 수도 모두 두 가지가 나오게 됩니다. 단, 위에서 구한 f'(2)일때를 제외해야 합니다. f'(2)는 3가지 경우의 수가 나왔었죠.
자, 이제 위에서 구한 f(3) 식의 형태를 따라 점화식을 구해보겠습니다.
여기서 n이 2일 때를 제외한 f'(n)은 모두 2이므로,
즉, f(n-1) ... f(0) 까지를 2로 묶고, f'(2) 와 연산되는 f(n-2)만 한 번 더 더해주면 되겠네요!
import sys
input = sys.stdin.readline
N = int(input().rstrip())
dp = [1, 2, 7, 22]
w_sum = 31
for i in range(4, N + 1):
dp.append((w_sum * 2 + dp[i - 2] + 2) % 1000000007)
w_sum += dp[-1]
print(dp[N] % 1000000007)
점화식에서 구한 대로 코드를 작성하면 위와 같습니다. f(3)까지는 미리 구했으므로 그대로 활용했습니다. 단 점화식에서의 합의 연속을 계속 누적합으로 구해줘야 하고, dp 배열을 업데이트 할 때마다 1000000007을 나눠주지 않으면 배열에서 너무 큰 수를 다루게 되어 메모리초과가 발생하게 됩니다. 이 점을 고려해서 점화식을 그대로 코드로 옮겨주시면 되겠습니다.
🙏 문제 접근 방법 및 코드에 대한 피드백과 질문은 환영입니다!
