[2602] 돌다리 건너기

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

분류 : DP

백준 2602 돌다리 건너기

모든 경우의수 구하기

---

구현 포인트

1) DP로 할 것

사실 이 문제는 DP라고 문제를 보자마자 알아채지 못했다. 아직 실력이 부족한 탓인가..

문제를 보고 상황 자체가 백트래킹 같아서 DFS로 접근을 하였다.

결과는 물론 시간초과;; 1초내에 몇 억이 될수있는 모든 경우를 DFS로 보기에는 역시..

주어진 조건에서 DFS로의 해결이 불가능 할꺼라는 것을 미리 잡았어야 했다.

일단 처음에 DFS로 구현했던 코드는 아래 같다.

#include<cstdio>
#include<cstring>
using namespace std;
 
char s[21];
int ind, cnt;
 
void getWay(char d[], char a[], int i) {
    if (ind == (int)strlen(s)) {
        cnt++;
        return;
    }
    int j, size = strlen(d);
    if (i >= size) return;
    for (j = i; j < size; j++) {
        if (d[j] == s[ind]) {
            ind++;
            getWay(a, d, j+1);
            ind--;
        }
    }
}
int main() {
    char d[101], a[101];
    fgets(s, 21, stdin);
    fgets(d, 101, stdin);
    fgets(a, 101, stdin);
    ind = 0;
    getWay(d, a, 0);
    ind = 0;
    getWay(a, d, 0);
    printf("%d\n", cnt);
}

그래서 결국 DP로 풀기로 했다. DP[i][j][k]를 k=0 이면 d로, 1이면 a로 끝나는 경우를 말하고,

주어진 d와 a를 i열까지 보았을 경우 두루마리의 문자열을 j까지 보는 경우를 담도록 했다.

#include <iostream>
#include<cstring>
using namespace std;
int main()
{
    char str[30], d[200], a[200];
    cin >> str >> d >> a;
    int dp[30][2] = { 1, 1 };
    int len = strlen(str), len_d = strlen(d);
    for (int i = 0; i < len_d; i++){
        for (int j = len - 1; j >= 0; j--){
            if (d[i] == str[j])
            {
                dp[j + 1][1] += dp[j][0];
            }
            if (a[i] == str[j])
            {
                dp[j + 1][0] += dp[j][1];
            }
        }
    }
    cout << dp[len][0] + dp[len][1] << endl;
    return 0;
}