알고리즘/동적 계획법

백준 2602 - 돌다리 건너기

hvv_an 2025. 7. 4. 10:57

문제 설명

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

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

출발 R I N G S R 도착
G R G G N S

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

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

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

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

출발 R I N G S R 도착
G R G G N S
출발 R I N G S R 도착
G R G G N S
출발 R I N G S R 도착
G R G G N S

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

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

 

 

 

 

 

 

제한 사항

 

 

 

 

 

 

풀이

문제를 요약하면 주문이 주어지고 2개의 다리에 대한 정보가 주어졌을 때 다리를 번갈아가며 주문을 만드는 경우의 수를 세는 것이다.

 

해당 문제는 DP를 사용하여 풀 수 있다.

DP에는 현재 다리의 인덱스와 만들어야 할 주문의 인덱스를 키로 만들 수 있는 경우의 수를 기록하면 된다.

이때 다리가 2개이기 때문에 최종적으로는 3차원 배열이 필요하다.

int dp[101][2][21];

 

이제 DFS를 통해 0번 인덱스부터 시작하여 주문을 하나씩 만들어 가면 된다.

0번을 시작으로 다리를 탐색할 것인데 만들어야 하는 주문과 일치한다면 다음으로 진행하면 된다.

int DFS(int idx, int bridge, int spellIdx)
{
	if (spellIdx == target.length()) return 1;

	int& ret = dp[idx][bridge][spellIdx];
	if (ret != -1) return ret;

	ret = 0;

	for (int i = idx; i < bridgeLen; i++)
	{
		if (bridge == 0)
		{
			if (devil[i] == target[spellIdx])
			{
				ret += DFS(i + 1, 1, spellIdx + 1);
			}
		}
		else
		{
			if (angel[i] == target[spellIdx])
			{
				ret += DFS(i + 1, 0, spellIdx + 1);
			}
		}
	}

	return ret;
}

다리를 번갈아가며 사용해야 하기 때문에 다리 유형에 따라 반대 다리로 DFS를 진행하면 된다.

 

이 과정을 악마의 다리와 천사의 다리를 시작으로 총 2번 진행하면 된다. 

int ans = DFS(0, 0, 0);
ans += DFS(0, 1, 0);

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9

using namespace std;
string target;
string angel, devil;
int bridgeLen;
int dp[101][2][21];

int DFS(int idx, int bridge, int spellIdx)
{
	if (spellIdx == target.length()) return 1;

	int& ret = dp[idx][bridge][spellIdx];
	if (ret != -1) return ret;

	ret = 0;

	for (int i = idx; i < bridgeLen; i++)
	{
		if (bridge == 0)
		{
			if (devil[i] == target[spellIdx])
			{
				ret += DFS(i + 1, 1, spellIdx + 1);
			}
		}
		else
		{
			if (angel[i] == target[spellIdx])
			{
				ret += DFS(i + 1, 0, spellIdx + 1);
			}
		}
	}

	return ret;
}

int main()
{
	INPUT_OPTIMIZE;
	
	cin >> target >> devil >> angel;

	bridgeLen = devil.length();
	memset(dp, -1, sizeof(dp));

	int ans = DFS(0, 0, 0);
	ans += DFS(0, 1, 0);

	cout << ans;

	return 0;
}