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

문제링크:https://www.acmicpc.net/problem/2602

2602번: 돌다리 건너기

 

dp문제입니다. 

두가지의 다리가 있고 

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

라는 규칙을 만족해야 합니다.

저는 각각 천사다리dp 와 악마다리dp를 만들어 문제를 해결했습니다.

 

RGS일때 

천사	R	I	N	G	S	R
1	1
2				1
3					1
앙마	G	R	G	G	N	S
1		1
2			1	1
3						2

 

와 같은 표를 만들 수 있습니다. 각 행의 값 dp[i][j] 는 dp[k][j-1]의 합이 됩니다. (k는 0~i까지 반복)

 

dp문제의 핵심은 점화식을 유도하는 것입니다.

 

이해가 되시지 않는다면 규칙과 표를 다시 한번 비교해보세요.

 

 정답코드입니다.

 

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

string a;
string angel;
string devil;

int dp[100][21] = { 0 };
int dp2[100][21] = { 0 };
int result = 0;
int main() {
	cin >> a;
	cin >> angel;
	cin >> devil;

	for (int i = 0; i < angel.size(); i++) {
		if (angel[i] == a[0]) dp[i][0] = 1;
		if (devil[i] == a[0]) dp2[i][0] = 1;
	}

	for (int i = 0; i < angel.size(); i++) {

		for (int j = 1; j < a.size(); j++) {
			if (angel[i] == a[j]) {
				int cnt = 0;
				for (int k = 0; k < i; k++)
					if (dp2[k][j - 1] != 0) cnt += dp2[k][j - 1];
				dp[i][j] = cnt;
			}
			if (devil[i] == a[j]) {
				int cnt = 0;
				for (int k = 0; k < i; k++)
					if (dp[k][j - 1] != 0) cnt += dp[k][j - 1];
				dp2[i][j] = cnt;
			}

		}

	}

	for (int i = 0; i < angel.size(); i++) {
		result += dp[i][a.size() - 1];
		result += dp2[i][a.size() - 1];
	}
	cout << result << endl;
}