[BOJ 2602] 돌다리 건너기

두루마리에 있는 문자열을 기반으로, 천사 혹은 악마의 돌다리를 건너야 한다.

 

 

 

전체적인 탐색이 필요하고, 탐색에서 중복으로 나타나는 유형은 메모이제이션이 필요하다.

 

 

 

메모이제이션을 위해서, 사용할 변수는 다음과 같다.

 

 

 

1. 천사 돌다리의 인덱스

2. 악마 돌다리의 인덱스

3. 두루마리 문자열의 인덱스

4. 다음 건너야 할 돌다리

 

 

 

이 4가지 변수는 메모이제이션에 있어서 꼭 필요한 것이다. 하나라도 누락된다면, 올바른 값이 다른 값으로 덮어씌워질 수 있다.

 

 

 

전체적인 탐색은, 두루마리의 문자열을 기반으로만 확인해주면 된다. 

 

 

 

중요한 것은, 돌다리를 하나 이상 건널 수 있다는 것을 유의해서 코드를 작성해야 한다.

 

 

 

해설코드(C++).

 

#include <iostream>
#include <cstring>
 
using namespace std;
 
string s1;
string s2;
string s;
 
int dp[102][102][21][3];
int answer = 0;
 
int func(int i1, int i2, int idx, int next){
    if(dp[i1][i2][idx][next] != -1)
        return dp[i1][i2][idx][next];
        
    if(idx == s.length()){
        return 1;
    }
        
    dp[i1][i2][idx][next] = 0;
    if(next == 1){
        for(int i = i2 + 1; i < s1.length(); i++){
            if(s1[i] == s[idx]){
                dp[i1][i2][idx][next] += func(i, i2, idx + 1, 2);
            }
        }
    }else{
        for(int i = i1 + 1; i < s2.length(); i++){
            if(s2[i] == s[idx]){
                dp[i1][i2][idx][next] += func(i1, i, idx + 1, 1);
            }
        }
    }
    
    return dp[i1][i2][idx][next];
}
 
int main() {
    cin >> s;
    cin >> s1;
    cin >> s2;
 
    memset(dp, -1, sizeof(dp));
    for(int i = 0; i < s1.length(); i++){
        if(s1[i] == s[0])
            answer += func(i,0,1,2);
    }
    
    for(int i = 0; i < s2.length(); i++){
        if(s2[i] == s[0])
            answer += func(0,i,1,1);
    }
 
    cout << answer << endl;
    return 0;
}