BOJ 2133 타일 채우기 / BOJ 13976 타일 채우기 2 / BOJ 14852 타일 채우기 3
이 포스트에서는 백준 Online Judge(BOJ)의 문제들 중에서도 "타일 채우기" 문제들을 풀어보도록 하겠습니다.
타일 채우기 문제란 주어지는 크기의 칸을 정해진 종류의 타일들로 채우는 경우의 수를 구하는 문제입니다.
일반적으로는 DP를 활용하여 해결을 하나, 어려운 문제의 경우에는 다른 전략을 같이 활용하여 문제를 해결할 수 있습니다.
백준 BOJ 2133번 : 타일 채우기
Solved.ac 난이도 : Gold V
알고리즘 분류 : DP
3×N 크기의 칸을 2×1, 1×2 타일들로 채우는 서로 다른 경우의 수를 구하는 문제입니다.
이 때 N ≤ 30입니다.
물론 채운 배열을 돌리거나 뒤집어서 같다고 하여 같은 경우의 수로 치지는 않습니다.
그렇기 때문에 DP를 활용하여 점화식으로 문제를 풀어주면 됩니다.
먼저 3×(홀수) 크기의 칸은 전체 칸의 수가 홀수이므로, 주어진 타일들만으로는 채울 수 없습니다.
이제 점화식을 세워야하는데, 먼저 dp[i] = dp[i-2] × 3 꼴로 세워볼 수 있습니다. (물론 여기에 추가로 더해줘야 함)
왜냐하면 dp[i-2]의 모든 경우의 수에 대해 dp[2] = 3이므로 각각 3가지 경우로 3 × 2 칸을 채울 수 있기 때문입니다.
그러나 예외가 존재하는데, 위와 같이 빨간색 네모 표시를 한 부분의 경우에는 3 × 2 크기의 칸으로 분리가 불가능한 조합입니다.
따라서 위와 같은 형태의 조합이 포함되어있는 경우도 추가로 더해주어야 합니다.
예를 들어 dp[i-4]에 위와 같은 형태 두 개를 붙일 수 있으므로 dp[i] += dp[i-4] × 2를 해주면 됩니다.
dp[i-6]에도 길이가 6인 위와 같은 조합을 만들어 붙일 수 있습니다.
이는 모든 i-(짝수) 크기의 배열에 조합 가능하므로, 반복문으로 j=i-4; j>=0; j-=2에 대해 dp[i] += dp[j] * 2를 수행해주면 됩니다.
#include<bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<int> dp(N+1);
dp[0] = 1, dp[2] = 3;
for(int i=4; i<=N; i+=2) {
dp[i] = dp[i-2] * 3;
for(int j=i-4; j>=0; j-=2) dp[i] += dp[j] * 2;
}
cout << dp[N];
}
백준 BOJ 13976번 : 타일 채우기 2
Solved.ac 난이도 : Platinum V
알고리즘 분류 : DP, 분할정복을 이용한 거듭제곱
역시 3×N 크기의 칸을 2×1, 1×2 타일들로 채우는 서로 다른 경우의 수를 구하는 문제이지만, 이번 문제의 경우에는 N ≤ 10^18입니다.
DP로 풀이한다고 하더라도 O(N)이고 이 역시 시간 초과가 발생합니다.
따라서 반드시 O(log N) 시간에 해결 가능한 풀이에 대해 고민해보아야 합니다.
가장 대표적인 방법은, 관계식을 찾은 뒤 행렬로 만들어 분할 정복을 이용한 거듭제곱으로 풀어주는 것입니다.
그러기 위해서는 우선 관계식을 찾아주어야 하는데, 항 몇 개를 직접 구한 뒤 OEIS(온라인 정수열 사전)를 활용해도 되고, 아니면 규칙성을 직접 찾아보아도 됩니다.
규칙성을 직접 찾기 위해서는 귀찮고 시간도 오래 걸리겠지만 N = 4 정도까지는 해보는 것을 추천합니다.
위의 필기는 제가 문제를 풀면서 대충 끄적인 내용인데, 대충 알아볼 수는 있으니 도움이 될 것 같아 첨부합니다.
문제를 거듭제곱에 대한 식으로 변환하여 풀이하기 위해 f(n)과 f(n-1)의 관계식의 계수를 행렬로 잡아 거듭제곱으로 표현할 수 있습니다.
따라서 위의 행렬의 빠른 거듭제곱만 구현해주면 f(N)을 log N 시간에 찾을 수 있게 됩니다.
#include<bits/stdc++.h>
#define MOD 1000000007
using namespace std;
typedef vector<vector<long long>> matrix;
matrix multiply(matrix &A, matrix &B) {
matrix C = {{0, 0}, {0, 0}};
for(int i=0; i<2; i++)
for(int j=0; j<2; j++)
for(int k=0; k<2; k++)
C[i][j] = (C[i][j] + A[i][k]*B[k][j] + MOD) % MOD;
return C;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
long long N; cin >> N;
if(N % 2 == 1) {
cout << "0\n";
return 0;
}
N /= 2;
matrix ans = {{1, 0}, {0, 1}}, A = {{4, -1}, {1, 0}};
while(N > 0) {
if(N % 2 == 1)
ans = multiply(ans, A);
A = multiply(A, A);
N /= 2;
}
cout << (ans[0][0] + ans[0][1]) % MOD;
}
행렬의 곱 연산의 구현은 다양한 방법이 있겠지만 위와 같이 2차원 벡터를 선언하고 이 벡터에 대한 multiply 함수를 구현해주는 것입니다.
행렬 A와 B의 곱 C의 C[i][j] = (A[i][k] * B[k][j]들의 합)으로 나타낼 수 있습니다.
마지막으로 n 제곱된 A 행렬을 A_n이라고 하면 f(n) = A_n(0, 0) * 1 + A_n(0, 1)이므로 해당 답을 출력해주면 됩니다.
백준 BOJ 14852번 : 타일 채우기 3
Solved.ac 난이도 : Gold V
알고리즘 분류 : DP
이번 문제는 2×N 크기의 공간을 2×1, 1×2, 1×1 크기의 타일들로 채우는 경우의 수를 구하는 문제입니다.
이 때 N은 100만 이하이고, mod 10^9 + 7 값을 구해주면 됩니다.
이 문제는 타일 채우기 1의 문제와 비슷한 풀이로 풀 수 있습니다.
조금 생각해보면, 우선 2×N 크기의 칸을 점화식으로 풀어본다고 하면, 2×(N-1)에는 2×1 타일 하나를 붙이는 경우 또는 1×1 타일 두 개를 붙이는 경우가 있고, 2×(N-2)에는 3가지 경우가 있고, 2×(N-3)부터는 "타일 채우기 1"에서 풀었던 분리되지 않는 2×3 크기의 조합을 2개 만들 수 있습니다. (2×(N-4)에서도, 2×(N-5)에서도 마찬가지)
따라서 점화식은 다음과 같습니다.
dp[i] = dp[i-1]×2 + dp[i-2]×3 + (dp[i-3]×2 + dp[i-4]×2 + ...)
이제 점화식을 세웠으니 풀어주기만 하면 되는데, 간단히 주의할 점은 dp에 대한 부분합을 따로 계산해주면서 for문을 돌려주어야 시간 낭비를 줄일 수 있습니다.
#include<bits/stdc++.h>
#define MAX 1000001
#define MOD 1000000007
using namespace std;
long long dp[MAX], sum[MAX];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
dp[0] = 1, dp[1] = 2, dp[2] = 7;
sum[0] = 1, sum[1] = 3, sum[2] = 10;
for(int i=3; i<=N; i++) {
dp[i] = (dp[i] + dp[i-1]*2 + dp[i-2]*3 + sum[i-3]*2) % MOD;
sum[i] = (dp[i] + sum[i-1]) % MOD;
}
cout << dp[N];
}