문제 요약
크기가 2 × 1인 직사각형 타일을 가로 또는 세로로 배치해 크기가 3 × n인 바닥을 빈틈없이 채우려고 한다.
바닥을 채울 수 있는 모든 경우의 수를 구하고, 결과를 1,000,000,007로 나눈 나머지를 반환해야 한다.
핵심 아이디어
이 문제는 작은 너비의 결과를 이용해 더 큰 너비의 결과를 구하는 동적 계획법 문제다.
먼저 3 × n 바닥의 전체 넓이는 다음과 같다.
3 × n타일 하나의 넓이는 2다.
바닥을 타일로 빈틈없이 채우려면 전체 넓이가 짝수여야 한다.
n이 홀수라면 3 × n도 홀수이므로 넓이가 2인 타일로 채울 수 없다.
n이 홀수인 경우: 0가지
n이 짝수인 경우: DP 계산따라서 짝수 길이에 대해서만 경우의 수를 계산하면 된다.
기본 경우
너비가 0인 경우
아무 타일도 놓지 않는 한 가지 방법이 있다고 정의한다.
dp[0] = 1이 값은 실제 입력에 대한 답을 구하기 위한 값이라기보다 점화식을 자연스럽게 만들기 위한 초기값이다.
너비가 2인 경우
3 × 2 바닥은 다음 세 가지 방법으로 채울 수 있다.
가로 타일 3개
위쪽에 가로 타일 2개 + 아래쪽에 세로 타일 2개
아래쪽에 가로 타일 2개 + 위쪽에 세로 타일 2개따라서 다음과 같다.
dp[2] = 3특수한 타일 배치
단순히 3 × 2 모양을 반복해서 붙이는 것만으로는 모든 경우를 만들 수 없다.
너비가 4 이상일 때는 양쪽 끝이 서로 맞물리는 특수한 모양이 존재한다.
각 짝수 너비마다 이런 특수한 배치는 두 가지씩 존재한다.
너비 4의 특수 배치: 2가지
너비 6의 특수 배치: 2가지
너비 8의 특수 배치: 2가지
...따라서 너비가 i일 때의 기본 점화식은 다음과 같다.
dp[i]
= 3 × dp[i - 2]
+ 2 × dp[i - 4]
+ 2 × dp[i - 6]
+ ...
+ 2 × dp[0]식으로 표현하면 다음과 같다.
dp[i] = 3 × dp[i - 2]
+ 2 × (dp[i - 4] + dp[i - 6] + ... + dp[0])3 × dp[i - 2]는 마지막 너비 2칸을 기본 세 가지 모양으로 채우는 경우다.
나머지 항들은 너비 4 이상인 특수 배치를 마지막에 붙이는 경우다.
점화식 최적화
기본 점화식을 그대로 구현하면 dp[i]를 계산할 때마다 이전 값을 여러 개 더해야 한다.
이 경우 전체 시간 복잡도가 O(n²)이 될 수 있다.
이전 점화식과의 차이를 이용하면 더 간단한 식을 만들 수 있다.
너비 i에 대한 식은 다음과 같다.
dp[i] = 3 × dp[i - 2]
+ 2 × (dp[i - 4] + dp[i - 6] + ... + dp[0])너비 i - 2에 대한 식은 다음과 같다.
dp[i - 2] = 3 × dp[i - 4]
+ 2 × (dp[i - 6] + ... + dp[0])두 식을 빼면 공통된 누적합 부분이 사라진다.
dp[i] - dp[i - 2]
= 3 × dp[i - 2] - 3 × dp[i - 4] + 2 × dp[i - 4]오른쪽 식을 정리하면 다음과 같다.
dp[i] - dp[i - 2]
= 3 × dp[i - 2] - dp[i - 4]따라서 최종 점화식은 다음과 같다.
dp[i] = 4 × dp[i - 2] - dp[i - 4]이제 각 값을 상수 시간에 계산할 수 있다.
풀이 과정
1. 홀수 길이 처리
n이 홀수라면 바닥의 넓이가 홀수이므로 타일로 채울 수 없다.
if n % 2 == 1:
return 02. 초기값 설정
dp_zero = 1
dp_two = 3각 변수는 다음 값을 의미한다.
dp_zero = dp[0]
dp_two = dp[2]3. 너비 2인 경우 처리
if n == 2:
return dp_two4. 짝수 너비만 계산
홀수 너비의 경우의 수는 항상 0이므로 4부터 2씩 증가하며 계산한다.
for width in range(4, n + 1, 2):최적화한 점화식을 적용한다.
current = (4 * dp_two - dp_zero) % MOD5. 이전 값 이동
다음 너비를 계산할 수 있도록 두 값을 한 단계씩 이동한다.
dp_zero, dp_two = dp_two, current예를 들어 dp[4]를 계산한 뒤에는 다음과 같이 변경된다.
dp_zero = dp[2]
dp_two = dp[4]다음 반복에서 dp[6]을 계산할 수 있다.
Python 코드
def solution(n):
MOD = 1_000_000_007
# 3 × 홀수 크기의 바닥은 채울 수 없다.
if n % 2 == 1:
return 0
# dp[0]과 dp[2]
dp_zero = 1
dp_two = 3
if n == 2:
return dp_two
# dp[i] = 4 * dp[i - 2] - dp[i - 4]
for width in range(4, n + 1, 2):
current = (
4 * dp_two - dp_zero
) % MOD
dp_zero, dp_two = dp_two, current
return dp_two코드 설명
나머지 상수
MOD = 1_000_000_007파이썬에서는 숫자 사이에 _를 넣어 큰 수를 읽기 쉽게 표현할 수 있다.
실제 값은 다음과 같다.
1000000007홀수 길이
if n % 2 == 1:
return 0바닥의 넓이가 홀수라면 넓이가 2인 타일을 몇 개 사용하더라도 정확히 채울 수 없다.
복잡한 DP 계산을 시작하기 전에 바로 0을 반환한다.
두 개의 DP 변수
dp_zero = 1
dp_two = 3현재 값을 계산할 때 필요한 것은 바로 앞의 짝수 길이 두 개뿐이다.
전체 DP 배열을 저장하지 않고 두 변수만 사용해 공간을 줄일 수 있다.
반복문이 진행된 뒤에는 변수의 의미가 다음과 같이 바뀐다.
dp_zero = dp[width - 2]
dp_two = dp[width]음수가 포함된 나머지 연산
current = (4 * dp_two - dp_zero) % MOD점화식에는 뺄셈이 포함되어 있다.
파이썬의 % 연산 결과는 음수가 되지 않으므로 그대로 작성해도 올바른 나머지를 얻을 수 있다.
다른 언어에서는 계산 결과가 음수라면 MOD를 더한 뒤 다시 나머지 연산을 해야 할 수 있다.
값 계산 예시
초기값은 다음과 같다.
dp[0] = 1
dp[2] = 3너비가 4인 경우는 다음과 같다.
dp[4]
= 4 × dp[2] - dp[0]
= 4 × 3 - 1
= 11너비가 6인 경우는 다음과 같다.
dp[6]
= 4 × dp[4] - dp[2]
= 4 × 11 - 3
= 41너비가 8인 경우는 다음과 같다.
dp[8]
= 4 × dp[6] - dp[4]
= 4 × 41 - 11
= 153따라서 n = 8일 때 바닥을 채우는 방법은 다음과 같다.
153가지시간 복잡도
짝수 너비만 2씩 증가하며 한 번 순회한다.
O(n)각 반복에서는 상수 횟수의 사칙연산만 수행한다.
n이 최대 5000이어도 충분히 빠르게 처리할 수 있다.
공간 복잡도
전체 DP 배열을 사용하지 않고 고정된 개수의 변수만 사용한다.
O(1)정리
이 문제는 특수한 타일 배치를 점화식에 포함해야 하는 동적 계획법 문제다.
풀이 흐름은 다음과 같다.
n이 홀수라면 0 반환
dp[0] = 1, dp[2] = 3으로 초기화
기본 점화식에 특수 배치 2가지씩 포함
누적합 형태의 점화식을 이전 식과 빼서 최적화
dp[i] = 4 × dp[i - 2] - dp[i - 4] 적용
각 단계에서 1,000,000,007로 나머지 연산단순히 3 × 2 모양을 반복하는 경우만 세면 특수한 타일 배치를 놓치게 된다.
특수 배치가 존재한다는 점을 파악하고, 누적 형태의 점화식을 O(1) 전이로 정리하는 것이 핵심이다.
