처음 봤을 때는 정확한 문제의 유형이 떠오르지 않았다. 그래서 이럴 때는 예시를 통해서 문제 풀이 방식을 생각해본다. 일단 주어진 예시에서 CAT TREE CATRTEE 였을 때를 생각해봤다.
과정을 생가해보면 완전 탐색으로 문제를 풀어야 할 것 같았다. CAT, TREE에서 현재 어디 위치를 가리키고 있는 포인터를 i,j 라고 하면 i,j를 움직이면서 CATRTEE를 만들어야 한다.
그래서 맨 처음에는 아무 위치를 가리키고 있지 않으니 0,0이고 i=1, j=0이라는 건 CAT에서 첫 번째 위치인 C를 가리키고 있고 CATRTEE에서 C까지 만들었다는 것을 의미한다. 이렇게 각 스탭에서 i를 움직일 것인지, j를 움직인 것인지를 판단하면 된다. 그런데 여기서 잘 생각해보면 완전 탐색을 하면서 i, j 의 값이 겹치는 경우들이 발생한다. 따라서 여기서 겹치는 부분 문제가 발생을 하기 때문에, 이 부분을 기록했다가 판단을 하면 모든 경우의 수를 탐색하지 않고 문제를 풀 수 있다. 따라서 dp 를 적용해서 문제를 풀 수 있다.
DP[i][j]를 첫 번째 단어에서 i 번째까지 사용이 되었고, 두 번째 단어에서 j 번째까지 사용되었을 때 타겟 문자를 만들 수 있는 지 없는 지로 정의했다.
import sys
dp = None
def solve(first, second, target, x, y):
if x + y == len(first) + len(second):
return True
if not dp[x][y]:
return dp[x][y]
a = False
b = False
next_x = x + 1
if next_x <= len(first) and first[next_x - 1] == target[next_x + y - 1]:
a = solve(first, second, target, next_x, y)
next_y = y + 1
if next_y <= len(second) and second[next_y - 1] == target[x + next_y - 1]:
b = solve(first, second, target, x, next_y)
dp[x][y] = a | b
return dp[x][y]
n = int(sys.stdin.readline())
for i in range(n):
words = sys.stdin.readline().strip().split(' ')
dp = [[True for _ in range(len(words[1])+1)]for _ in range(len(words[1])+1)]
if (solve(words[0], words[1], words[2],0,0)) :
print(f'Data set {i+1}: yes')
else:
print(f'Data set {i+1}: no')
