1. 1x2 2x1 타일 (백준 11726)
2. 1x2 2x1 2x2 타일 (백준 11727)
3. 1x2 2x1 2x2 타일 응용 (백준 1720, 1793)
4. 3XN 타일 (백준 2133)
5. 4XN 타일 (백준 2718)
---------------
1. 1x2 2x1 타일 (백준 11726)
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
입력
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
출력
첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
예제 입력
2
예제출력
2
예제 입력
9
예제 출력
25
풀이
- 타일문제는, i-1 혹은 i-2까지 채워졌다고 가정했을 때, 주어진 타일을 가지고 몇가지 경우 수로 타일을 채울 수 있는가를 생각해보는 게 문제풀이 핵심
- 이 문제의 경우, 2x1타일 (세로로 세워진것)을 가지고, i-1까지 채워지고 한 칸 남았을 때 채울 수 있는 방법 수가 1개, 1x2 타일을 가지고는, 2칸 남았을 때 채울 수 있는 방법이 1개(1x2를 2개 가로로 눕혀서)이기에, 점화식이 다음과 같이 된다.
D[i] = D[i-1] + D[i-2] ;피보나치 수열과 동일한 형태가 됨
소스
#include <stdio.h>#include <algorithm>#define MOD 10007using namespace std;int N;int a[1003];int D[1003];int solve() { D[0] = 0; D[1] = 1; D[2] = 2; for (int i = 3; i <= N; ++i) { D[i] = D[i - 1] + D[i - 2]; if (D[i] > MOD) D[i] %= MOD; } return D[N];}int main() { scanf("%d", &N); printf("%d\n", solve()); return 0;}2. 1x2 2x1 2x2 타일 (백준 11727)
2×n 직사각형을 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×17 직사각형을 채운 한가지 예이다.
입력
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
출력
첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
예제 입력 2
예제 출력 3
예제 입력 8
예제 출력 3171
예제 입력 12
예제 출력 2731
풀이
- 2x1을 가지고 한 칸 남았을 때 1가지, 1x2타일을 가지고 두 칸 남았을 때 1가지 방법, 2x2타일을 가지고 두 칸 남았을 때 1가지. 따라서, 점화식은,
D[i] = D[i-1] + D[i-2] * 2
소스
#include <stdio.h>#define MOD 10007int N;int main() { int a, b, c; scanf("%d", &N); if (N == 1) { printf("1\n"); return 0; } if (N == 2) { printf("3\n"); return 0; } a = 1; b = 3; for (int i = 3; i <= N; ++i) { c = 2*a + b; if (c >= 10007) c %= MOD; a = b; b = c; } printf("%d\n", c);}3. 1x2 2x1 2x2 타일 응용 (백준 1720, 1793)
2×N 크기의 넓은 판을 1×2 (또는 2×1) 크기와 2×2 크기의 타일로 채우려고 한다. 여러 가지 경우가 있을 수 있으므로, 각각을 하나의 코드로 대응시켜서 암호화에 이용하려고 한다.
그런데 문제가 생겼다. 넓은 판을 교환하다 보니 좌우 대칭인 경우가 있어, 뒤집히는 경우 코드가 헷갈리게 되는 경우가 발생한 것이다. 예를 들어 아래의 두 경우는 달라 보이지만 좌우 대칭을 이루고 있다.
N이 주어지면, 전체 타일 코드의 개수를 구하는 프로그램을 작성하시오. (단, 서로 좌우 대칭을 이루는 중복된 표현은 한 가지 경우로만 처리한다.)
입력
첫째 줄에 타일의 크기 N(1≤N≤30)이 주어진다.
출력
첫째 줄에 타일 코드의 개수를 출력한다.
예제 입력
4
예제 출력
8
풀이
- 중복된 경우의 수를 어떻게 세는 지가 핵심.
- 먼저 중복을 고려하지 않았을 때의 경우의 수를 구해서 D[i]에 넣는다.
D[i] = D[i-1] + 2 * D[i-2] ; (2x1)에 대해 한칸남았을 때 1가지, (1x2)와 (2x2)에 대해 두 칸 남았을 때 각각 한 가지씩
- 이제 중복되는 경우를 생각해봐야는데, 생각을 약간 달리해서 중복되지 않는 것을 생각해보면 구할 방법이 생긴다.
즉, 중복되지 않는 것들은 모양새가 자체 대칭성을 가지는 것들.
(3칸 짜리를 생각해보면 2x1 타일이 3개 연속으로 있는 것이 자체 대칭성있는것)
- 이제 문제는 이렇게 바꿔서 생각할 수 있게 되었다.
중복되지 않는 타일모양 수 = (전체 모양 수 + 중복되지 않는 것들 수) / 2
==> 중복되는 것들은 2개씩 있고, 중복되지 않는 것들은 1개씩 있으니깐, 중복 안되는 것들을 더 더해주고, 전체에서 2로 나누면 되는 것 (수식으로 이해해보면, T=A+2B에서, (A+2B+A)/2=(A+B) )
- 중복되지 않는, 자체 대칭성이 있는 것들은, 전체 칸 수에서 가운데를 나눠서 그 반쪽에 대한 경우의 수로 생각할 수 있다.
좀 더 세밀하게 보면 짝수인경우와 홀수인 경우로 나눠서 생각해야는데,
1)홀수개의 경우는, (예를 들어 5칸이면)
가운데인 3번째 칸 하나에 2x1 타일을 위치시키고, 양쪽 2칸씩에 대해 가질 수 있는 경우의 수로 생각하면,(자체대칭인 수를 S[i]라하자)
S[i] = D[i/2] //(i-1)/2 가 정확하겠으나, 그냥 i/2도 동일 결과.
2)짝수의 경우는 (예를 들어 6칸이면)
반쪽인 왼쪽 3칸과 오른쪽 3칸으로 나눴을 때 나올 수 있는 경우의 수랑,
가운데 2칸에 (1x2) 2개 넣어진 경우랑, (2x2) 한개 넣어진 경우를 중심으로 해서, 양쪽으로 2칸씩 해서 나올 수 있는 경우의 수의 합
S[i] = D[i/2] + 2 * D[i/2 -1] = D[i/2 + 1] //D[i/2+1]로 되는 것은, 점화식의 정의를 이용해서 간단히 한 것임
소스
#include <stdio.h>int N, D[31],S[31],i;int main() { scanf("%d",&N); D[1]=1; D[2]=3; for(i=3;i<=N;++i) D[i]=D[i-1]+2 * D[i-2]; S[1]=1; S[2]=3; for(i=3;i<=N;++i){ if ((i%2)==0) S[i]=(D[i]+D[i/2 + 1])/2; else S[i]=(D[i]+D[i/2])/2; } printf("%d\n",S[N]); return 0;}4. 3XN 타일 (백준 2133)
2×N 크기의 벽을 2×1(그리고 1×2) 크기의 타일로 채우는 경우의 수를 구하는 문제는 쉽다. 그렇다면 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.
입력
첫째 줄에 N(1≤N≤30)이 주어진다.
출력
첫째 줄에 경우의 수를 출력한다.
예제 입력 복사
2
예제 출력 복사
3
힌트
아래 그림은 3×12 벽을 타일로 채운 예시이다.
풀이
- 2개 남았을 때 3가지 방법있음.
근데, 4개, 6개, 8개 ... 가 남았을 때, 위 2개 남았을 때의 모양과 다른, 고유의 경우의 수가 있고, 각각 2개씩임.
(위 그림을 보면 중간에 4칸에 대해 고유의 모양이 형성될 수 있음을 알 수 있음. 뒤 집으면 2종류)
- 따라서, 점화식을 세우면 다음과 같이 됨
D[i] = 3 * D[i-2] + Sum(2 * D[k]), i-4 >= k >= 0, k -= 2,
D[0]=1, D[1]=0, D[2]=3, D[3]=0
소스
#include <stdio.h>int N,D[31];int main() { int i, k; scanf("%d", &N); D[0] = 1; D[2] = 3; for (i = 4; i <= N; i += 2) { D[i] = 3 * D[i - 2]; for (k = (i - 4); k >= 0; k -= 2) D[i] += (2 * D[k]); } printf("%d\n", D[N]); return 0;}5. 4XN 타일 (백준 2718)
- 4개일 때는 3가지
- 정리해보면 다음과 같다.
#include <stdio.h>#include <vector>using namespace std;int T,N;int m[2] = {3,2};int main() { int t, i, j, k; scanf("%d", &T); for (t = 1; t <= T; ++t) { scanf("%d", &N); vector<int> D(N+1,0); if (N == 1) { printf("1\n"); continue; } if (N == 2) { printf("5\n"); continue; } D[0] = 1; D[1] = 1; D[2] = 5; for (i = 3; i <= N; ++i) { D[i] = D[i - 1] + 4 * D[i - 2]; for (k = 3; k <= i; ++k) D[i] += (m[k % 2] * D[i-k]); } printf("%d\n", D[N]); } return 0;}