[백준] 2602번 : 돌다리 건너기 (C++)

2602번 : 돌다리 건너기 

---

문제)

절대반지를 얻기 위하여 반지원정대가 출발한다. 원정대가 지나가야할 다리는 두 개의 인접한 돌다리로 구성되어 있다. 하나는 <악마의 돌다리>이고 다른 하나는 <천사의 돌다리>이다.

아래 그림 1은 길이가 6인 다리의 한 가지 모습을 보여준다. 그림에서 위의 가로줄은 <악마의 돌다리>를 표시하는 것이고, 아래의 가로줄은 <천사의 돌다리>를 표시한다. 두 돌다리의 길이는 항상 동일하며, 각 칸의 문자는 해당 돌에 새겨진 문자를 나타낸다. 두 다리에 새겨진 각 문자는 {R, I, N, G, S} 중 하나이다.

 

 

반지원정대가 소유하고 있는 마법의 두루마리에 <악마의 돌다리>와 <천사의 돌다리>를 건너갈 때 반드시 순서대로 밟고 지나가야할 문자들이 적혀있다. 이 순서대로 지나가지 않으면 돌다리는 무너져 반지원정대는 화산 속으로 떨어지게 된다.

다리를 건널 때 다음의 제한 조건을 모두 만족하면서 건너야 한다.

1. 왼쪽(출발지역)에서 오른쪽(도착지역)으로 다리를 지나가야 하며, 반드시 마법의 두루마리에 적힌 문자열의 순서대로 모두 밟고 지나가야 한다.
2. 반드시 <악마의 돌다리>와 <천사의 돌다리>를 번갈아가면서 돌을 밟아야 한다. 단, 출발은 어떤 돌다리에서 시작해도 된다.
3. 반드시 한 칸 이상 오른쪽으로 전진해야하며, 건너뛰는 칸의 수에는 상관이 없다. 만일 돌다리의 모양이 그림 1과 같고 두루마리의 문자열이 "RGS"라면 돌다리를 건너갈 수 있는 경우는 다음의 3가지 뿐이다. (아래 그림에서 빨간색 문자는 밟고 지나가는 돌다리를 나타낸다.)

 

 

아래의 세 방법은 실패한 방법이다.

 

 

왜냐하면 첫 번째는 문자열 "RGS"를 모두 밟고 지나가야 하는 조건 1)을 만족하지 않으며, 두 번째는 번갈아가면서 돌을 밟아야 하는 조건 2)를, 세 번째는 앞으로 전진을 하여야하는 조건 3)을 만족하지 않기 때문이다.

 

마법의 두루마리에 적힌 문자열과 두 다리의 돌에 새겨진 문자열이 주어졌을 때, 돌다리를 통과할 수 있는 모든 가능한 방법의 수를 계산하는 프로그램을 작성하시오. 예를 들어, 그림 1의 경우는 통과하는 방법이 3가지가 있으므로 3을 출력해야 한다.

 

 

 

 

입력 :

첫째 줄에는 마법의 두루마리에 적힌 문자열(R, I, N, G, S 로만 구성된)이 주어진다. 이 문자열의 길이는 최소 1, 최대 20 이다. 그 다음 줄에는 각각 <악마의 돌다리>와 <천사의 돌다리>를 나타내는 같은 길이의 문자열이 주어진다. 그 길이는 1 이상, 100 이하이다.

 

 

 

출력 :

마법의 두루마리에 적힌 문자열의 순서대로 다리를 건너갈 수 있는 방법의 수를 출력한다. 그러한 방법이 없으면 0을 출력한다.

모든 테스트 데이터에 대한 출력결과는 2^31-1 이하이다.

 

 

 

 

 

 

풀이)

 

탑다운 풀이

// 2602. 돌다리 건너기
#include <iostream>
#include <string>
 
using namespace std;
 
int n;
int iScroll;
 
string scroll;
string a, b;
 
long long dp[110][25][2];
 
long long recur(int cur, int idx, int pos)
{
    if (cur == n)
    {
        if (idx == iScroll) return 1;
        return 0;
    }
 
    if (dp[cur][idx][pos] != -1) return dp[cur][idx][pos];
 
    long long ret = 0;
    
    if (pos == 0)
    {
        if (idx < iScroll && scroll[idx] == a[cur])
        {
            ret += recur(cur + 1, idx + 1, 1);
        }
        ret += recur(cur + 1, idx, 0);
    }
    else if (pos == 1)
    {
        if (idx < iScroll && scroll[idx] == b[cur])
        {
            ret += recur(cur + 1, idx + 1, 0);
        }
        ret += recur(cur + 1, idx, 1);
    }
 
    dp[cur][idx][pos] = ret;
 
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> scroll;
    cin >> a >> b;
    fill(&dp[0][0][0], &dp[109][24][2], -1);
 
    n = a.length();
    iScroll = scroll.length();
 
    long long ans = 0;
    for (int i = 0; i < 2; i++) ans += recur(0, 0, i);
    cout << ans;
 
    return 0;
}

 

 

바텀업 풀이

 

// 2602. 돌다리 건너기
#include <iostream>
#include <string>
 
using namespace std;
 
int n;
int iScroll;
 
string scroll;
string a, b;
 
long long dp[110][25][2];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> scroll;
    cin >> a >> b;
 
    n = a.length();
    iScroll = scroll.length();
 
    dp[n][iScroll][0] = 1;
    dp[n][iScroll][1] = 1;
 
    for (int cur = n - 1; cur > -1; cur--)
    {
        for (int idx = iScroll; idx > -1; idx--)
        {
            for (int pos = 1; pos > -1; pos--)
            {
                long long& ret = dp[cur][idx][pos];
 
                if (pos == 0)
                {
                    if (idx < iScroll && scroll[idx] == a[cur])
                    {
                        ret += dp[cur + 1][idx + 1][1];
                    }
                    ret += dp[cur + 1][idx][0];
                }
                else if (pos == 1)
                {
                    if (idx < iScroll && scroll[idx] == b[cur])
                    {
                        ret += dp[cur + 1][idx + 1][0];
                    }
                    ret += dp[cur + 1][idx][1];
                }
            }
        }
    }
 
    cout << dp[0][0][0] + dp[0][0][1];
 
    return 0;
}

---

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

2602번: 돌다리 건너기