문제요약

영어 소문자와 숫자로 구성된 문자열 $S$와 $T$가 주어진다.

$S$에 아래 연산을 단 한 번만 사용해서 약어를 만들 수 있다.

• 서로 겹치지 않는 비어 있지 않은 부분문자열을 $0$개 이상 고른다.
• 선택한 부분문자열을 각각 그 길이에 해당하는 십진수 문자열로 바꾼다.
• 이때 십진수 문자열은 0으로 시작할 수 없다.

$S$에 주어진 연산을 사용해 만든 약어로 $T$가 가능한지 판별해 보자.

풀이

$S$에서 $i$개, $T$에서 $j$개 사용했을 때 서로 일치 할 수 있는가에 대한 정보를 저장한다.

백트래킹 느낌으로 구현하였다.

정답코드

#include <bits/stdc++.h>

using namespace std;

string s,t;
int visited[2020][2020];
int n,m;
int flg;

void dfs(int i, int j){
    if (i == n && j == m) flg = 1;
    if (i >= n || j >= m) return;
    if (visited[i][j]) return;
    visited[i][j] = 1;

    if (s[i] == t[j]) dfs(i+1, j+1);

    int last = -1;
    for (int k = j; k < m; k++){
        if (k - j + 1 >= 5) break;
        if (!('0' <= t[k] && t[k] <= '9')){
            last = k;
            break;
        }
    }
    if (last == -1) last = m;

    for (int k = j; k < last; k++){
        if (k-j+1 >= 5) break;
        int num = stoi(t.substr(j, k-j+1));
        if (num == 0) break;
        dfs(i + num, k+1);
    }
}

int main(){
    cout.sync_with_stdio(0); cin.tie(0);

    cin >> s;
    cin >> t;
    n = s.size();
    m = t.size();

    dfs(0, 0);

    if (flg) cout << "Yes";
    else cout << "No";

    return 0;
}