2602 돌다리 건너기

#include <stdio.h>
#include <string>
#include <iostream>
#include <algorithm>
 
using namespace std;
 
string part, arr1, arr2;
int dp[25][3][105] = { 0 };
 
int main() {
    getline(cin, part);
    getline(cin, arr1);
    getline(cin, arr2);
 
    for (int j = 0; j < arr1.size(); j++) {
        if (part[0] == arr1[j]) {
            dp[0][1][j] = 1;
        }
 
        if (part[0] == arr2[j]) {
            dp[0][2][j] = 1;
        }
    }
 
    for (int k = 1; k < part.size(); k++) {
        for (int j = 0; j < arr1.size(); j++) {
            if (part[k] == arr1[j]) {
                int sum = 0;
                for (int t = 0; t < j; t++) {
                    sum += dp[k - 1][2][t];
                }
 
                dp[k][1][j] = sum;
            }
 
            if (part[k] == arr2[j]) {
                int sum = 0;
                for (int t = 0; t < j; t++) {
                    sum += dp[k - 1][1][t];
                }
 
                dp[k][2][j] = sum;
            }
        }
    }
    
    int rst = 0;
    for (int i = 0; i < arr1.size(); i++) {
        rst += dp[part.size() - 1][1][i];
        rst += dp[part.size() - 1][2][i];
    }
    printf("%d", rst);    
}