[Algorithm]Baekjoon 2602번 :: 돌다리 건너기

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

2602번: 돌다리 건너기

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
string target;
string bridges[2];
int dp[2][101][21] = { 0 };
 
int DFS(int curIndex, int targetIndex, int isDevilBridge)
{
    if (dp[isDevilBridge][curIndex][targetIndex] != -1) return dp[isDevilBridge][curIndex][targetIndex];
    if (targetIndex == target.size()-1) return 1;
 
    dp[isDevilBridge][curIndex][targetIndex] = 0;
    int otherBridge = (isDevilBridge + 1) % 2;
 
    for (int i = curIndex + 1; i < bridges[0].size(); ++i)
    {
        if (bridges[otherBridge][i] == target[targetIndex + 1])
        {
            dp[isDevilBridge][curIndex][targetIndex] += DFS(i, targetIndex + 1, otherBridge);
        }
    }
 
    return dp[isDevilBridge][curIndex][targetIndex];
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    string s1, s2, s3;
    cin >> s1 >> s2 >> s3;
 
    target = " " + s1;
    bridges[0] = " " + s2;
    bridges[1] = " " + s3;
 
    memset(dp, -1, sizeof(dp));
 
    cout << DFS(0, 0, 0) + DFS(0, 0, 1);
}

 

꽤나 스탠다드한 유형의 문제라 생각한다.

앞으로 나아갈 때 번갈아가면서 이동해야하는데, 타겟문자열의 순서에 맞게 이동했을 때 전부 맞춰야 우측다리로 건너갈 수 있다.

 

중복되는 경우를 피하기위해 dp를 3차원으로 했다.

1차는 어느쪽 다리인지 (악마다리인지 천사다리인지)

2차는 현재 다리의 몇번째까지 왔는지

3차는 타겟문자열의 몇번째까지 진행했는지(맞췄는지)

 

이다.