알고리즘 :: 백준 :: DP :: 9177 :: 단어 섞기

문제

문제 링크

세 개의 단어가 주어졌을때, 꿍은 첫 번째 단어와 두 번째 단어를 섞어서 세 번째 단어를 만들 수 있는지 궁금해졌다. 첫 번째와 두 번째 단어는 마음대로 섞어도 되지만 원래의 순서는 섞여서는 안 된다. 다음과 같은 경우를 생각해보자.

• 첫 번째 단어 : cat
• 두 번째 단어 : tree
• 세 번째 단어 : tcraete

보면 알 수 있듯이, 첫 번째 단어와 두 번째 단어를 서로 섞어서 세 번째 단어를 만들 수 있다. 아래와 같이 두 번째 예를 들어보자.

• 첫 번째 단어 : cat
• 두 번째 단어 : tree
• 세 번째 단어 : catrtee

이 경우 역시 가능하다. 그렇다면 "cat"과 "tree"로 "cttaree"를 형성하는건 불가능하다는걸 눈치챘을 것이다.

문제접근

• 두 문자열을 '인터리빙(Interleaving)'하는 문제다.
• 15483번 '최소 편집'과 유사한 유형의 DP 문제다. (https://velog.io/@embeddedjune/알고리즘-백준-DP-15483-최소-편집)
• 우리의 DP 전략은 다음과 같다.
  • 두 문자열 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"; 
	}
}

결과