[BOJ 2602] 돌다리 건너기

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

발은 두개니까 두발로 두줄의 돌다리를 건너는 문제이다 (규칙은 문제를 읽어보도록 ...)

해당 문제의 경우 dp테이블을 3차원으로 dp[위쪽인지 아래쪽인지][몇번째 문자열인지][몇번째로 밟았는지] 로 정의할 수 있다.

간략하게 dp점화식을 세운다면 dp[위쪽][i번쨰 문자열][j번쨰로 밟은경우] += dp[아래쪽][i-1번째 문자열][j-1번쨰로 밟은경우] 이런식이다.

#include<iostream>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<utility>
#include<vector>
#include<cstring>
#include<queue>
#include<cmath>
#include<math.h>
#define INF 1e9
typedef unsigned long long ll;
 
using namespace std;
 
string s,s1,s2;
int dp[4][111][111]; // (위 아래) / 몇번쨰문자열인지 / 몇번째 숫자인지
 
 
int main(){
    cin >> s >> s1 >>s2;
    
    for(int i=0;i<s1.length();i++){
        if(s[0] == s1[i]){
            dp[1][i][0]++;
        }
        if(s[0] == s2[i]){
            dp[2][i][0]++;
        }
    }
    
    for(int i=0;i<s.length();i++){
        for(int j=0;j<s1.length();j++){
            if(s[i] == s1[j]){
                for(int k= j+1;k<s1.length();k++){
                    if(s[i+1] == s2[k]){
                        dp[2][k][i+1] += dp[1][j][i];
                    }
                }
            }
            if(s[i] == s2[j]){
                for(int k= j+1;k<s1.length();k++){
                    if(s[i+1] == s1[k]){
                        dp[1][k][i+1] += dp[2][j][i];
                    }
                }
            }
        }
    }
    
    int ans= 0;
    for(int i=0;i<s1.length();i++){
        ans += dp[1][i][s.length()-1] +dp[2][i][s.length()-1];
    }
    
    cout <<ans <<endl;
    
}