[백준 2602] 돌다리 건너기 - Java

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

2602번: 돌다리 건너기

---

문제설명

 

 

문제접근

이 문제는 완전탐색으로 접근할 수 있지만, 성능이 매우 나빠져 시간초과가 발생합니다.

동적계획법을 사용하면 O(NM) 시간만에 문제를 해결할 수 있습니다. (N = 다리의 길이, M = 두루마리의 길이)

DP[다리][현재 다리 위치][두루마리 위치] = 현재 다리 위치에서 해당 두루마리 위치까지 이동 가능한 모든 경우의 수를 담습니다.

 

점화식은 다음과 같습니다. (악마의 돌다리도 동일합니다)

 

현재 다리 위치 i에 있는 글자가 두루마리 j위치의 글자와 일치하는 경우

ANGEL[i][j] = ANGEL[i-1][j] + DEVIL[i-1][j-1]

 

현재 다리 위치 i에 있는 글자가 두루마리 j위치의 글자와 일치하지 않는 경우

ANGEL[i][j] = ANGEL[i-1][j]

 

위 점화식을 사용하면 마지막 다리 위치의 두루마리 마지막 인덱스가 구하고자 하는 값이 됩니다.

 

소스코드

public class BOJ_2602_돌다리건너기 {
    public static final int ANGEL = 0, DEVIL = 1;
 
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
 
        String magicScroll = sc.nextLine();
        String angel = sc.nextLine();
        String devil = sc.nextLine();
 
        System.out.println(solve(angel, devil, magicScroll));
 
    }
 
    /**
     *
     *  @문제접근
     *  동적계획법으로 풀었습니다.
     *  각 인덱스에서 각각의 두루마리 문자에 대응하는 경우의 수를 누적해서 구하고
     *  dp배열의 마지막 인덱스에 두루마리 문자 전체를 사용한 경우의 수를 반환합니다.
     *
     *  @성능
     *  Runtime: 104 ms
     *  Memory Usage: 14224 KB
     *  시간복잡도: O(두루마리 길이 * 다리길이) = O(NM)
     *
     */
    private static int solve(String angel, String devil, String magicScroll) {
        int[][][] dp = new int[2][angel.length()][magicScroll.length()];
 
        // 기저사례
        if(angel.charAt(0) == magicScroll.charAt(0))
            dp[ANGEL][0][0] = 1;
        if(devil.charAt(0) == magicScroll.charAt(0))
            dp[DEVIL][0][0] = 1;
 
        for(int i = 1; i < angel.length(); i++){
 
            dp[ANGEL][i][0] = angel.charAt(i) == magicScroll.charAt(0) ? dp[ANGEL][i-1][0] + 1 : dp[ANGEL][i-1][0];
            for(int j = 1; j < magicScroll.length(); j++)
                dp[ANGEL][i][j] = angel.charAt(i) == magicScroll.charAt(j) ? dp[ANGEL][i-1][j] + dp[DEVIL][i-1][j-1] : dp[ANGEL][i-1][j];
 
            dp[DEVIL][i][0] = devil.charAt(i) == magicScroll.charAt(0) ? dp[DEVIL][i-1][0] + 1 : dp[DEVIL][i-1][0];
            for(int j = 1; j < magicScroll.length(); j++)
                dp[DEVIL][i][j] = devil.charAt(i) == magicScroll.charAt(j) ? dp[DEVIL][i-1][j] + dp[ANGEL][i-1][j-1] : dp[DEVIL][i-1][j];
        }
 
        return dp[DEVIL][devil.length()-1][magicScroll.length()-1] + dp[ANGEL][angel.length()-1][magicScroll.length()-1];
    }
}