백준[2602] 돌다리 건너기

문제 설명

문제 링크

http://icpc.me/2602

2602번: 돌다리 건너기

풀이

dp를 이용하여 풀이할 수 있다.

dp는 dp[악마다리 or 천사다리][몇 번째 패턴 문자까지 발견][몇 번째 돌다리까지 갔나]로 정의할 수 있다.

코드

#include <iostream>
#include <string>

using namespace std;

int dp[2][22][100];
string pat, a, b;

int dpf(int up_down, int pat_num, int cur_num) {
    int &ret = dp[up_down][pat_num][cur_num];
    
    if (ret) return ret;
    if (pat_num == pat.length() - 1) return 1;
    
    if (up_down) {
        for (int i = cur_num + 1; i < a.length(); i++) {
            if (a[i] == pat[pat_num + 1]) ret += dpf(0, pat_num + 1, i);
        }
    } else {
        for (int i = cur_num + 1; i < a.length(); i++) {
            if (b[i] == pat[pat_num + 1]) ret += dpf(1, pat_num + 1, i);
        }
    }
    
    return ret;
}

int main() {
    cin >> pat;
    cin >> a >> b;
    int ans = 0;
    for (int i = 0; i < a.length(); i++) {
        if (a[i] == pat[0]) ans += dpf(0, 0, i);
        if (b[i] == pat[0]) ans += dpf(1, 0, i);
    }
    printf("%d", ans);
}