백준 2718번 타일 문제 state를 cache로 저장하는 DP

 

4*N타일을 채우는 문제로처음 문제를 접근할때

1번째 타일부터 채우면서 N번째 타일까지 dfs를 하면서  같은 타일 번째의 같은 상태에서 또 계산할 필요가 없어

이 부분을 cache에 저장하는 방법을 상용하려 했는데,

 

문제의 경우 test case로 여러 케이스를 연달아 풀어야합니다. 위 방법 접근법은 cache의 재활용이 안되므로,

 

dfs를 몇 번째 타일을 접근중이 아닌, 남은 타일의 개수로 셌습니다.

 

타일 딱 N번째 한줄만 생각했을때 놓을 수 있는 방법의 수가 많지 않고 규칙성도 바로 떠오르지 않으므로

 

그냥 직접 손으로 몇개 세어줍니다.

여러 타일의 상태에 따라서 놓을수 있는 경우의 수는 총 6개 정도 나오고

각 경우마다 다음 타일에 주는 영향을 상태를 다음 dfs함수에 넘겨줍니다.

상태는 5가지 정도 나옵니다.

 

 

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;



int cache[101][5];

int T;
int N;


// test case마다 cahce를 사용하면 좋으므로
// 각 앞으로 남은 타일 수와 상태수로 매개변수를 넘겨주자

// st = 0은 가장 앞 타일이 모두 empty
// st = 1은 위 2타일이 empty
// st = 2은 밑에 2타일이 empty
// st = 3은 가운데 2타일이 empty
// st = 4은 맨위, 맨아래 각 1타일이 emtpy
/*
0  1  2  3  4

o  o  x  x  o 

o  o  x  o  x

o  x  o  o  x

o  x  o  x  o
*/

//1 과 2는 대칭형태로 경우의 수가 같으므로 같은 캐시를 공유해도 된다. 이 문제풀이에서는 다른 캐시로 처리


//tile개수가 남고 맨앞 타일이 st상태일때
int dp(int tile, int st) {
	if (tile == 0 && st == 0) return 1;
	if (tile == 0 && st) return 0; //마지막 타일이 삐져나올 경우 0
	if (tile < 0) return 0;

	if (cache[tile][st] != -1) return cache[tile][st];
	int res;

	//현재 타일 상태에서 맨앞에 타일을 꽉채우고 다음 타일로 넘어가는 경우의 수
	switch (st) {
		
		// 맨앞 타일을 5가지 형태로 채울 수 있음
		//그때 다음 타일의 상태로 dp 진행
		case 0:
			res = dp(tile - 1, 0) + dp(tile - 1, 1) + dp(tile - 1, 2) + dp(tile - 1, 3) + dp(tile - 2, 0);
			break;
		
		//2가지 경우 가능
		case 1:
			res = dp(tile - 1, 0) + dp(tile - 1, 2);
			break;
		
        //2가지 경우 가능
		case 2:
			res = dp(tile - 1, 0) + dp(tile - 1,1);
			break;
       
		//2가지 경우 가능
		case 3:
			res = dp(tile - 1, 0) + dp(tile - 1, 4);
			break;

		//1가지 경우 밖에 둘 수 없음
		case 4:
			res = dp(tile - 1, 3);
	}

	return cache[tile][st] = res;

}

int main() {
	ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
	// -1로 모두 채움
    // memset은 byte단위로 채우기 때문에 0과 -1만 가능합니다.
    // 혹은 char형태 배열만 가능
	memset(cache, -1, sizeof(cache));

	cin >> T;

	for (int i = 0; i < T; ++i) {
		cin >> N;
		cout << dp(N, 0)<<"\n";
	}

}