[ boj : 2602 ] 돌다리 건너기

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

2602번: 돌다리 건너기

해설 : 천사 돌다리와 악마 돌다리가 나뉘어져 있으니깐 전 2번 탐색하였습니다.

두루마리에 적힌 문자열대로 번갈아가면서 탐색해야되니, 상태들을 3차원 배열로 표현을 해주면 됩니다.

 

dp[x][y][cnt] = a 문자열을 x번째까지 탐색과 b 문자열을 y번째까지 탐색이 cnt 번째일때 만들 수 있는 경우의 수

 

만약 현재 내가 찾고자 하는 문자가 맞다면 선택을 하고 다음 돌다리로 가야되니 (i+1,i+1)로 건너간 후에 다시 탐색해 주면 되겠죠.

 

기저조건은 depth가 두루마리에 적힌 문자열길이 일때 return 1 시켜주면 되겠고요.

 

그냥 전형적인 dp 문제인데 문제는 왜 3차원으로 만들어야 하냐는 겁니다.

만약 2차원으로 만들었다면, 

 

aaa

aaaa

aaaa

 

와 같은 케이스에선 두루마리에 적힌 문자열 aaa 가 전부 확인이 되어야지 1을 리턴시켜줘야 하지만, 도중에 aa 두번째까지만 탐색했을 경우에도 이미 dp 테이블에 값이 저장되어있기 때문에 해당 값을 return 시켜버리는 불상사가 발생할 수 있기 때문입니다.

 

그러니 1차원을 하나 더 추가하여 몇번째 depth 일때 도달하였는지 체크를 해주어야 합니다.

 

#include<bits/stdc++.h>

using namespace std;

string str,a,b;
int dp[110][110][20];

int f(int x, int y, bool flag, int pos);

int main()
{
	memset(dp, -1, sizeof(dp));
	cin >> str >> a >> b;
	//cout << f(0, 0, 0,false,0) + f(0, 0, 1,true,0);
	int x = f(0, 0, false, 0);
	memset(dp, -1, sizeof(dp));
	int y = f(0, 0, true, 0);
	cout << x + y;
	return 0;
}
int f(int x, int y,bool flag,int pos)
{
	if (pos >= str.length())return 1;
	if (x >= a.length() || y >= b.length())return 0;

	int& ret = dp[x][y][pos];
	if (ret != -1)return ret;

	ret = 0;
	if (!flag) {
		for (int i = y; i < b.length(); i++)
			if (b[i] == str[pos])
				ret += f(i + 1, i+1, !flag, pos + 1);
	}
	else {
		for (int i = x; i < a.length(); i++)
			if (a[i] == str[pos])
				ret += f(i + 1, i + 1, !flag, pos + 1);
	}
	return ret;
}