문제 풀이

bfs로도 풀 수 있어 보이나 일단은 바텀 업 dp방식으로 풀어봤다.

dp[i][j] = 첫 문자열에서 i개 만큼 사용하고, 두 번째 문자열에서 j개 만큼 사용했을 때 세 번째 문자열의 i+j까지 사용할 수 있는지 여부를 저장하는 dp 배열이다.

예제

cat tree tcraete

에서 dp[0][1]은 두 번째 문자열을 1개 사용했을 때이고, 두 번째 문자열의 첫 번째 원소 't'를 사용해서 세 번째 문자열의 1번째 까지 만들 수 있으므로 dp[0][1] = true다.

dp[1][0]은 첫 번째 문자열을 1개 사용했을 때이고, 첫 번째 문자열의 첫 번째 원소 'c'를 사용해서 세 번째 문자열의 1번째 까지 만들 수 없으므로 ('c' != 't') dp[1][0] = false다.

좀 더 나아가 보자,
dp[1][1]은 첫 번째 문자열과 두 번째 문자열 모두 처음부터 한 개씩 사용했을 때 문자열 'tc'를 만들 수 있는지 없는지의 여부다.

그렇다면 이것은 두가지의 경우의 수로 나뉜다.

• 첫번째 문자열을 하나도 사용하지 않고, 두 번째 문자열을 하나만 사용했을 때 't'를 만들 수 있고, 첫 번째 문자열 하나를 사용해서 세 번째 문자열의 두 번째 원소인 'c'를 만들 수 있다면 dp[1][1] = true다.
• 즉, dp[0][1] = true이고, 첫 번째 문자열의 첫 번째 원소는 'c'이고 세 번째 문자열의 두 번째 원소는 'c'로, 'c' = 'c' 이므로 dp[1][1] = true다.

또 다른 한 가지의 경우의 수는

• dp[1][1]은 첫 번째 문자열의 첫 번째 원소를 사용하고, 두 번째 문자열의 원소를 하나도 사용하지 않았을때 세 번째 문자열의 첫 원소인 't'를 만들 수 있고(dp[1][0] == true 이면), 두 번째 문자열의 원소를 하나('t')를 사용해서 세 번째 문자열의 두 번째 원소인 'c'를 만들 수 있다면 dp[1][1] = true다.

• 즉, dp[1][0] = true이고, 두 번째 문자열의 첫 번째 원소는 't'이고 세 번째 문자열의 두 번째 원소 'c'와 같다면 dp[1][1] = true지만, dp[1][0] = false 인데다가 't' != 'c' 이므로 두 조건 모두 성립하지 않는다.

하지만 두 가지의 경우의 수 중 하나라도 성립한다면 만들 수 있는 것이므로 최종적으로 dp[1][1]= true다.

이런 논리를 토대로 알고리즘을 짜면 아래의 코드와 같다.

✔ 주의할점
문자열의 인덱스는 0부터 시작하지만 생각의 편의상 그리고 코딩의 편의상 dp배열에서 인덱스는 1부터 시작한다.
즉, 첫번째 문자열을 a, 두 번째 문자열을 b라고 했을 때, dp[1][1] = a[0]까지 사용하고, b[0]까지 사용 했을 때 c[1]까지의 문자열을 만들 수 있는지의 여부다.

문제 링크

boj/9177

소스코드

PS/9177 .java

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

class Main {
  static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

  static boolean [][]dp = new boolean[202][202];
  public static void main(String[] args) throws Exception {
    int n = Integer.parseInt(br.readLine());
    for(int i=0;i<n;i++) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      String a = st.nextToken();
      String b = st.nextToken();
      String c = st.nextToken();
      for(int j=0;j<=a.length();j++)
        Arrays.fill(dp[j], false);
      if(a.charAt(0) == c.charAt(0))
        dp[1][0] = true;
      if(b.charAt(0) == c.charAt(0))
        dp[0][1] = true;
      for(int j=0;j<=a.length();j++)
      {
        for(int k=0;k<=b.length();k++)
        {
          if (j>=1 && dp[j-1][k] && c.charAt((j+k-1)) == a.charAt(j-1))
            dp[j][k] = true;
          if(k>=1 && dp[j][k-1] && c.charAt((j+k-1)) == b.charAt(k-1))
            dp[j][k] = true;
        }
      }
      bw.write("Data set " + (i+1)+": "+(dp[a.length()][b.length()]?"yes\n":"no\n"));
    }
    bw.flush();
  }
}