[JAVA]백준 2602번: 돌다리 건너기

www.acmicpc.net/problem/2602

2602번: 돌다리 건너기

1. 문제 설명

 

돌다리 2개가 주어지고 마법의 두루마리 문자열이 주어졌을 때 마법의 두루마리 문자열의 순서대로 돌다리를 건너야 한다.

 

돌다리 건너는 규칙은 네 가지가 있는데

 

1. 왼쪽에서 오른쪽으로 이동하며, 주어진 마법의 두루마리 문자열에 적힌 순서대로 모두 밟고 가야 한다.

2. 돌다리 2개를 번갈아 가면서 건너야 한다.

3. 건너뛰는 칸의 수는 상관이 없다.

4. 한 칸 이상 오른쪽으로 전진해야 한다.

 

문자열과 돌다리가 주어질 때 돌다리를 건널 수 있는 방법의 가짓수를 구하는 문제이다.

 

2. 풀이

 

메모이제이션을 이용하여 풀 수 있다.

 

dp [돌다리 2개][마법의 두루마리 길이][돌다리 길이] : 현재의 마법의 두루마리 위치와 현재의 돌다리 위치까지 가능한 가지의 수.

 

dp 배열을 사용하여 현재 돌다리 위치에서 그 전 위치로 가능한 값들을 더해준다.

 

만약, 현재 돌다리 위치의 글자와 마법의 두루마리 위치의 글자가 동일하다면

 

dp[돌다리][마법의 두루마리 위치][돌다리 위치]=dp [돌다리][마법의 두루마리 위치][돌다리 위치 -1]+dp [다른 돌다리][마법의 두루마리 위치-1][돌다리 위치-1]을 하면 된다.

 

현재 돌다리 위치에서 1을 뺴는 이유는 1을 빼지 않으면 규칙 4번을 어기고 중복이 생길 수 있기 때문이다.

 

3. 코드

import java.awt.image.BufferedImageFilter;
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class Main {




    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


        String magic=br.readLine();


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

        int magic_size=magic.length();
        int str_size=devil.length();

        int[][][] dp = new int[2][magic_size][str_size];

        if(magic.charAt(0)==devil.charAt(0))
            dp[0][0][0]=1;
        if(magic.charAt(0)==angel.charAt(0))
            dp[1][0][0]=1;

        for(int x=1;x<str_size;x++){


            char devil_temp=devil.charAt(x);
            char angel_temp=angel.charAt(x);

            dp[0][0][x]=dp[0][0][x-1];
            dp[1][0][x]=dp[1][0][x-1];
            
            if(devil_temp==magic.charAt(0))
                dp[0][0][x]+=1;
            if(angel_temp==magic.charAt(0))
                dp[1][0][x]+=1;
            
            for(int y=1;y<magic_size;y++){

                dp[0][y][x] += dp[0][y][x - 1];
                dp[1][y][x] += dp[1][y][x - 1];

                if(devil_temp==magic.charAt(y))
                    dp[0][y][x]+=dp[1][y-1][x-1];
                if(angel_temp==magic.charAt(y))
                    dp[1][y][x]+=dp[0][y-1][x-1];
                
            }


        }


        bw.write(String.valueOf(dp[0][magic_size - 1][str_size-1] + dp[1][magic_size - 1][str_size-1]));

        bw.flush();
        bw.close();
        br.close();


    }

}