아방가르드 타일링
https://school.programmers.co.kr/learn/courses/30/lessons/181186
문제 설명
3×N 보드에 타일을 빈틈없이 채우는 경우의 수를 구하는 문제입니다.
주어지는 정수 n에 대해 보드를 채우는 방법의 수를 1,000,000,007로 나눈 나머지를 반환합니다.
타일은 다양한 모양(ㄴ자, ━자 등)으로 배치될 수 있습니다.
단, 보드의 크기는 항상 세로 3, 가로 N의 형태이며, N은 정수입니다.
문제 분석
단순한 2×N 타일링 문제와는 달리 패턴이 복잡하고, 다양한 유니크한 조합이 존재합니다.
N이 커질수록 가능한 조합이 기하급수적으로 늘어납니다.
이 문제는 단순 재귀 혹은 반복문으로는 풀 수 없으며, 적절한 점화식을 세워 DP 방식으로 풀어야 합니다.
핵심 아이디어 및 점화식
점화식 도출
문제는 단순한 피보나치 형태의 점화식이 아니라 다음과 같은 복합 점화식을 사용합니다:
dp[n] = dp[n-1] + dp[n-2] * 2 + dp[n-3] * 6 + dp[n-4] - dp[n-6]dp[i]는 3×i 타일을 채우는 방법의 수를 의미합니다.
기존 패턴과 새롭게 추가되는 블록 구조를 모두 고려해야 하므로 다항 점화식 형태로 설계되었습니다.
마지막 - dp[n-6]는 중복되는 블록 조합 제거를 위한 보정입니다.
계산 도중 음수가 발생할 수 있으므로, 항상 mod 연산을 수행해야 합니다.
초기 조건
패턴의 구조상, 최소한의 초기값은 아래와 같이 수기로 정의합니다:
dp[0] = 1;
dp[1] = 1;
dp[2] = 3;
dp[3] = 10;
dp[4] = 23;
dp[5] = 62;최종 코드
function solution(n) {
const mod = 1000000007;
const dp = [1, 1, 3, 10, 23, 62];
for (let i = 6; i <= n; i++) {
dp[i] = (dp[i - 1] + dp[i - 2] * 2 + dp[i - 3] * 6 + dp[i - 4] - dp[i - 6] + mod) % mod;
}
return dp[n];
}