[BOJ] 2133번: 타일 채우기

1. problem : 

https://www.acmicpc.net/problem/2133

 

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
int d[33];

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n; 
	d[0] = 1, d[2] = 3;
	for (int i = 3; i <= n; i++) {
		d[i] += d[i - 2] * 3;
		for (int j = i - 4; j >= 0; j -= 2) {
			d[i] += d[j] * 2;
		}
	}
	cout << d[n];
}

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x10/solutions/2133.cpp

basic-algo-lecture/0x10/solutions/2133.cpp at master · encrypted-def/basic-algo-lecture

dp를 이용해 풀었다. 따라서, 세 가지 스텝을 따른다. 

1. 테이블을 정의한다. d[i] = 가로길이가 i일 때의 경우의 수 

2. 점화식을 작성한다. d[i] = d [i-2] * 3 + (d [i-4] + d [i-6] +... + d [i-k]) * 2 (단 i - k >= 0) 

3. 초기값을 설정한다. d[0] = 1, d [2] = 3 

2번이 핵심이다. 왜 저런식이 나올까? 

일단, d[i-2] * 3인 이유는 홀수일 때는 0이기 때문에 신경 쓰지 않고, 짝수일 때만 고려하면 된다. 따라서, i-2번째 block에 d [2] 값을 곱해주면 된다. 따라서, d [2] = 3이기 때문에, 3을 곱해준다. 그 뒤에 식은 특수패턴의 처리이다. 

d [4]일 때부터 특수패턴이 나온다. 이때, 특수패턴은 가로길이가 4인 특수패턴이다. 이 특수패턴은 1*2블록만을 사용하여 윗변 또는 밑변을 구성할 때 나타난다. 따라서, 2가지 특수패턴이 있다. 여기서 더 나아가, d [6]일 때는 가로길이가 6인 특수패턴과 가로길이가 4인 특수패턴을 가질 수 있다. 이때도 마찬가지로, 가로길이가 6인 특수패턴은 2가지가 나온다. 

따라서, d[6] = d [4] * 3 + d [2] * 2 + d [0] * 2로 표현할 수 있다.