Algorithm/BOJ
[BOJ]2133번: 타일 채우기(c++)
HBGB
2020. 4. 24. 18:11
https://www.acmicpc.net/problem/2133
2133번: 타일 채우기
문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 입력 첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다. 출력 첫째 줄에 경우의 수를 출력한다. 예제 입력 1 복사 2 예제 출력 1 복사 3 힌트 아래 그림은 3×12 벽을 타일로 채운 예시이다....
www.acmicpc.net
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
#include <iostream>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// 변수 선언, 입력
int const MAX = 30;
int const len2 = 3;
int tiles[MAX + 1] = {0, };
int n;
cin >> n;
/*
점화식
D[i] : 3 * i 를 1*2, 2*1로 채우는 방법의 수
Type 1 : 3*2를 채우는 방법
Type 2 : 각 길이에 2개씩 방법이 더 있다
--> D[i] = D[i - 2] * 3 + D[i - 4] * 2 + D[i - 6] * 2 ...
*/
tiles[0] = 1;
for (int i = 2; i <= n; i += 2)
{
tiles[i] = tiles[i - 2] * len2;
for (int j = i - 4; j >= 0; j -= 2)
{
tiles[i] += tiles[j] * 2;
}
}
cout << tiles[n];
return 0;
}
Colored by Color Scripter
|
처음에 너무 복잡하게 생각해서 D[i][j]로 이차원 배열을 만들다가 망했다.
D[i]을 그림으로 표현하자면 다음과 같다.
그림을 그려가다보면 4, 6 ... 번째에 생기는 특이한 그림이 있다.
저런거/뒤집은거 해서 2개씩 생긴다.
그걸 차차 더해주면 됨..
그림으로 나타내면 아래와 같다.
홀수번째는 만들수 없다.