백준 9177번 C++ 풀이

문제

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

시간 제한	메모리 제한	solved.ac 티어
1초	256MB	골드 4

사진을 클릭하면 문제로 이동합니다.

---

풀이

 dfs + dp로 풀었다. 첫번째 단어를 a, 두번째를 b, 세번째를 c라고 하자. c의 첫번째 글자은 a의 첫번째 글자이거나, b의 첫번째 글자일 것이다. 둘다일수도 있다. 현재 사용된 이 알파벳이 a일때와 b일때를 구분해서 계속 dfs로 들어가면서, 최종적으로 c를 만들 수 있는지를 판단한다. dfs를 하면서 지금 사용해야하는 a와 b, c의 인덱스를 인자로 넘겨준다. 이때, 재귀를 하면서 a, b의 같은 인덱스를 여러번 탐색할 수도 있다. 예를 들어, 다른 탐색에서 a와 b의 인덱스가 각각 1, 2일때 불가능함을 알았을때, 다른 경로로 1, 2에 다시 왔다면, 볼 이유가 없기 때문이다. 

 

코드

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

string a, b, c;
int memo[201][201];

int sol(int i = 0, int j = 0, int k = 0) {
	if (k == c.length()) {
		return 1;
	}

	if (memo[i][j] != -1) {
		return memo[i][j];
	}

	bool check_a = i < a.length() && c[k] == a[i];
	bool check_b = j < b.length() && c[k] == b[j];

	if (check_a && check_b) {
		return (memo[i + 1][j] = sol(i + 1, j, k + 1)) | (memo[i][j + 1] = sol(i, j + 1, k + 1));
	}
	else if (check_a) {
		return memo[i + 1][j] = sol(i + 1, j, k + 1);
	}
	else if (check_b) {
		return memo[i][j + 1] = sol(i, j + 1, k + 1);
	}
	else {
		return 0;
	}
}

int main() {
	cin.tie(0)->sync_with_stdio(false);
	int tc; cin >> tc;
	for(int i = 1; i <= tc; ++i) {
		cin >> a >> b >> c;
		memset(memo, 0xff, 201*201*sizeof(int));
		cout << "Data set " << i << ": " << (sol() ? "yes" : "no") << endl;
	}
}