세 개의 단어가 주어졌을때, 꿍은 첫 번째 단어와 두 번째 단어를 섞어서 세 번째 단어를 만들 수 있는지 궁금해졌다. 첫 번째와 두 번째 단어는 마음대로 섞어도 되지만 원래의 순서는 섞여서는 안 된다. 다음과 같은 경우를 생각해보자.
보면 알 수 있듯이, 첫 번째 단어와 두 번째 단어를 서로 섞어서 세 번째 단어를 만들 수 있다. 아래와 같이 두 번째 예를 들어보자.
이 경우 역시 가능하다. 그렇다면 "cat"과 "tree"로 "cttaree"를 형성하는건 불가능하다는걸 눈치챘을 것이다.
lhs, rhs
을 행과 열로 하는 2차원 배열을 만들고 각 (i, j)
요소는 해당 길이까지의 두 부분 문자열로 세 번째 단어를 만들 수 있는지 없는지를 boolean 값으로 표현할 것이다.0번째 행
을 보자true
.c
인데, (0, 1)
의 lhs = "", rhs = "t"
이므로 세 번째 문자열을 만들 수 없다는 것을 알 수 있다. 따라서 false
.a
인데, (0, 2)
의 lhs = "", rhs = "tr"
이므로 세 번째 문자열을 만들 수 없다는 것을 알 수 있다. 따라서 false
.이제 0번째 열
을 보자.
c
인데, (1, 0)
의 lhs = "c", rhs = ""
이므로 세 번째 문자열과 일치하므로 true
.a
인데, (0, 2)
의 lhs = "ca", rhs = ""
이므로 세 번째 문자열과 일치하므로true
.lhs="c", rhs="t"
인 경우를 생각해보자. 두 문자열로는 세 번째 문자열의 "ca"
를 만들 수 없음을 알 수 있다.lhs
의 i
번째 문자와 rhs
의 j
번째 문자와 세 번째 문자열의 i + j - 1
번째 문자를 비교해서lhs
와 같은지lhs
와 같다면, 윗쪽 칸((i - 1, j)
)의 결과를 가져온다. 왜냐하면, 윗쪽 칸은 lhs
의 i
번째 문자가 없을 때의 결과를 의미하는데 여기에 i
번째 문자를 추가해준 것과 같기 때문에 결과를 그대로 따라가기 때문이다. 글로는 이해가 힘든데 직접 표를 딱 한 번만 그려보면 감이 잡힐 것이다.rhs
와 같은지rhs
와 같다면, 왼쪽 칸((i, j - 1)
)의 결과를 가져온다. 위와 동일한 이유로 rhs
의 j
번째 문자를 추가해준 것과 같기 때문이다.lhs
에서 왔는지 rhs
에서 왔는지 알 수 없다. 따라서 둘 (위쪽, 왼쪽) 중 하나라도 true
가 있다면 그대로 가져온다.lhs
와 rhs
의 조합으로는 아직 만들 수 없기 때문에 false
처리한다.true
면 lhs
와 rhs
로 세 번째 문자열을 만들 수 있다는 것이므로 문제 조건에 맞는 형식으로 값을 출력한다.#include <iostream>
using namespace std;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, loop = 1;
cin >> n;
while (n--) {
string a, b, c;
cin >> a >> b >> c;
int lLen = a.length(), rLen = b.length();
bool memo[lLen + 1][rLen + 1];
memo[0][0] = true;
for (int i = 1; i <= lLen; ++i) memo[i][0] = (a[i - 1] == c[i - 1]) ? memo[i - 1][0] : false;
for (int i = 1; i <= rLen; ++i) memo[0][i] = (b[i - 1] == c[i - 1]) ? memo[0][i - 1] : false;
for (int i = 1; i <= lLen; ++i) {
for (int j = 1; j <= rLen; ++j) {
char curA = a[i - 1], curB = b[j - 1], curC = c[i + j - 1];
if (curA != curC && curB != curC) memo[i][j] = false;
else if (curA == curC && curB != curC) memo[i][j] = memo[i - 1][j];
else if (curA != curC && curB == curC) memo[i][j] = memo[i][j - 1];
else memo[i][j] = memo[i - 1][j] || memo[i][j - 1];
}
}
cout << "Data set " << loop++ << ": ";
(memo[lLen][rLen]) ? cout << "yes\n" : cout << "no\n";
}
}