2602번: 돌다리 건너기

https://www.acmicpc.net/problem/2602


$O(mn)$ m: 두루마리 문자열 길이, n: 돌다리 길이

dp[i][j][k]: 1...i 칸 j(악마/천사) 돌다리에 도착했을 때까지 k개의 돌을 밟았을 경우의 수

#include<cstdio>
char m[21], s[2][101];
int dp[21][2] = { 1,1 }, l;
int main() {
    scanf("%s%s%s", m, s, s[1]);
    while (m[++l]);
    for (int i = 0; s[0][i]; i++) for (int j = l; j--;) {
        dp[j + 1][0] += (s[0][i] == m[j])*dp[j][1];
        dp[j + 1][1] += (s[1][i] == m[j])*dp[j][0];
    }
    printf("%d", dp[l][0] + dp[l][1]);
    return 0;
}