[BAE/<JOON> 문제풀이] 2602. 돌다리 건너기

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

2602번: 돌다리 건너기

 

핵심::

DP 점화식 찾기

 

풀이::

DP 문제는 점화식 찾는거 밖에 적을 풀이 내용이 없음.

 

dp배열 : dp[돌다리 번호][윗돌다리 : 0, 아래 돌다리 : 1][마법두루마리 글자 번호] = 해당하는 경로 갯수

 

점화식 : 현재 경로 개수 : sum(이전 경로 개수)

if 현재 돌다리(n) 문자가 k번째 돌다리 문자와 같다면

-> dp[n][0][k] = sum( dp[0 ~ n - 1][1][k - 1] )

-> dp[n][1][k] = sum( dp[0 ~ n - 1][0][k - 1] ) 

 

코드::

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;
int dp[101][2][21];

int main()
{
	string p, u, d;
	cin >> p;
	cin >> u;
	cin >> d;
	int n = u.size();
	int pn = p.size();
	int dap = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < pn; j++) {
			if (u[i - 1] == p[j]) {
				if (j == 0) {
					dp[i][0][j] += 1;
				}
				if (j > 0) {
					for (int k = 1; k < i; k++) {
						dp[i][0][j] += dp[k][1][j - 1];
					}
				}
				if (j == pn - 1) {
					dap += dp[i][0][j];
				}
			}
			if (d[i - 1] == p[j]) {
				if (j == 0) {
					dp[i][1][j] += 1;
				}
				if (j > 0) {
					for (int k = 1; k < i; k++) {
						dp[i][1][j] += dp[k][0][j - 1];
					}
				}
				if (j == pn - 1) {
					dap += dp[i][1][j];
				}
			}
		}
	}

	cout << dap;

	return 0;
}