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

문제

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

아래 그림 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을 출력해야 한다.

입력

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

출력

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

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

예제 입력 1 복사

RGS RINGSR GRGGNS

예제 출력 1 복사

3

---

dp 문제이다. 

dfs로 할 수도 있으나 for문을 통해 bottom-up 방식으로 해결했다. 

 

dp 배열은 3차원으로 각각 (입력 문자열 index) (악마/천사 다리) ( 다리 indx) 를 뜻한다.

다리의 문자와 입력 문자가 같으면 그 이전 문자까지의 dp를 모두 구해서 입력하면 된다.

글로 설명하기가 힘드니 예시를 주자면, 입력 문자열 RGS와 악마/천사 다리 RINGSR / GRGGNS에서 

입력 문자열의 두번째 문자 G를 생각해보자. 악마 다리에서 G가 같은 곳은 네 번째 글자이다. 따라서 천사 다리의 1~3번째 글자에서 입력 문자열의 첫번째 문자 R의 갯수를 구한다. 천사 다리에서는 G가 같은곳이 세군데가 있고 악마 다리에서 R은 한개이므로 두가지 경우가 가능하다. S도 마찬가지로 S가 같은 곳 이전 인덱스에서 가능한 G의 개수를 구하면 된다.

이런 식으로 for 문을 이용해 해결할 수 있었다.

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%EB%8F%8C%EB%8B%A4%EB%A6%AC%20%EA%B1%B4%EB%84%88%EA%B8%B0%20(2602%EB%B2%88).cpp

chosh95/STUDY

 

C++ 코드

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int dp[21][2][101]; // (입력 문자열)(악마/천사)(다리 인덱스)
char p[2][101]; // (악마/천사)(다리)
char origin[21]; // 입력 문자열

int originLen, bridgeLen;

int main()
{
	string tmp;
	cin >> tmp;
	originLen = tmp.size();
	for (int i = 1; i <= tmp.size(); i++)
		origin[i] = tmp[i - 1];

	cin >> tmp;
	bridgeLen = tmp.size();
	for (int i = 1; i <= tmp.size(); i++)
		p[0][i] = tmp[i - 1];
	
	cin >> tmp;
	for (int i = 1; i <= tmp.size(); i++)
		p[1][i] = tmp[i - 1];


	for (int j = 0; j <= 1; j++) {
		for (int k = 1; k <= bridgeLen; k++) {
			if (p[j][k] == origin[1]) {
				dp[1][j][k] = 1;
			}
		}
	}

	for (int i = 2; i <= originLen; i++) {
		for (int j = 0; j <= 1; j++) {
			for (int k = 1; k <= bridgeLen; k++) {
				if (p[j][k] == origin[i]) {
					int cnt = 0;
					for (int m = 1; m < k; m++) {
						cnt += dp[i - 1][1 - j][m];
					}
					dp[i][j][k] = cnt;
				}
			}
		}
	}

	int res = 0;
	for (int i = 0; i <= 1; i++) {
		for (int j = 1; j <= bridgeLen; j++) {
			res += dp[originLen][i][j];
		}
	}
	cout << res;
}