돌다리 건너기 - 2602번

---

풀이 방법

먼저 재귀적으로 완전탐색을 이용해서 풀었다. 하지만 시간초과가 나오고 말았다.

그래서 DP를 추가해 주었다. 

DP는 [현재 밟은 곳][찾고 있는 문자 인덱스][돌다리 종류] 로 나타내었다.

 

예제 입력 3번을 예로 들자면

 

GGGGRRRR   GGGGRRRR   GGGGRRRR  GGGGRRRR 

SSSSGGGG   SSSSGGGG   SSSSGGGG   SSSSGGGG 

 

이렇게 찾은 후 다음 G에서

 

GGGGRRRR    GGGGRRRR   GGGGRRRR    GGGGRRRR

SSSSGGGG    SSSSGGGG    SSSSGGGG    SSSSGGGG

 

똑같이 반복 될것이다. 그래서 위쪽의 돌다리에서 3번째 G를 밟은 후 현재는 아래쪽의 처음 나오는 G를 밟고 있으면 현재 밟은 곳에서 찾고 있는 문자가 인덱스와 돌다리의 종류가 같은 케이스가 나온적이 있으므로 DP에 저장된 값을 가지고 오는 것이다.

 

내 코드

package com.company;

import java.io.*;
import java.util.*;


public class Main {
    static String angel;
    static String devil;
    static String str;
    static int cnt;
    static int[][][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        str = br.readLine();
        devil = br.readLine();
        angel = br.readLine();

        cnt = 0;
        dp = new int[str.length()][devil.length()+1][2];
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                Arrays.fill(dp[i][j], -1);
            }
        }

        cnt += fff(0, 0, 1);
        cnt += fff(0, 0, 0);

        System.out.println(cnt);
    }

    static int fff(int index, int s, int c) {
        if (str.length() == s) {
            return 1;
        }
        if (dp[s][index][c] > -1) {
            return dp[s][index][c];
        }

        int total = 0;
        if (c == 1) {
            for (int i = index; i < devil.length(); i++) {
                if (str.charAt(s) == devil.charAt(i)) {
                    total += fff(i + 1, s + 1, 0);
                }
            }
        } else {
            for (int i = index; i < devil.length(); i++) {
                if (str.charAt(s) == angel.charAt(i)) {
                    total += fff(i + 1, s + 1, 1);
                }
            }
        }
        return dp[s][index][c] = total;
    }

}