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

문제 바로가기 > 2602번: 돌다리 건너기

 

완전탐색하면 시간초과가 나므로 dp를 사용해야 한다.

 

문제 설정

두 개의 다리 angleBridge와 devilBridge가 있으며, 원하는 값 answer 대로 발판을 밟아 가며 끝까지 건너야 한다. 이때, 다리를 건너널 때는 두 개의 다리를 번갈아가면서 건너야 한다.

DP 배열 설정

dp[bridge][i][j]

• bridge: 현재 위치한 다리를 나타내며, 0은 악마의 돌다리, 1은 천사의 돌다리
• i: answer에서 현재까지 진행한 문자의 인덱스.
• j: 각 다리에서 현재 확인하고 있는 발판의 인덱스.

초기화

• dp[0][0][n] 및 dp[1][0][n]은 각 다리의 시작점에서 아직 어떤 문자도 밟지 않은 상태를 나타내므로 1로 초기화

DP 점화식

• 일치: 만약 현재 다리의 j번째 발판이 answer의 i번째 문자와 일치한다면,
  • dp[현재 다리][i][j] = dp[현재 다리][i][j-1] + dp[다른 다리][i-1][j-1]
  • 여기서 dp[현재 다리][i][j-1]는 같은 다리에서 이전 발판에서 현재 문자를 이미 사용한 경우의 수, dp[다른 다리][i-1][j-1]은 다른 다리에서 이전 문자를 사용하고 현재 다리로 이동한 경우의 수를 나타낸다.
• 불일치: 만약 현재 다리의 j번째 발판이 route의 i번째 문자와 일치하지 않는다면,
  • dp[현재 다리][i][j] = dp[현재 다리][i][j-1]
  • 이는 현재 발판이 answer 문자열에 포함되지 않으므로 이전 발판에서의 값만을 가져온다.
• 천사다리를 먼저 선택한 경우와 악마다리를 먼저 선택한 경우가 있으므로 각 경우를 더해주어야 한다.
• result = dp[0][route.length()][a.length()] + dp[1][route.length()][b.length()]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class _2602 {

    public static void main(String[] args) throws Exception {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String answer=br.readLine();
        String devilBridge=br.readLine();
        String angleBridge=br.readLine();

        int[][][] dp=new int[2][answer.length()+1][devilBridge.length()+1];
        Arrays.fill(dp[0][0], 1);
        Arrays.fill(dp[1][0],1);

        for(int i=1;i<=answer.length();i++){
            for(int j=1;j<=devilBridge.length();j++){
                if(answer.charAt(i-1)==devilBridge.charAt(j-1)){
                    dp[0][i][j]=dp[0][i][j-1]+dp[1][i-1][j-1];
                }else{
                    dp[0][i][j]=dp[0][i][j-1];
                }
                if(answer.charAt(i-1)==angleBridge.charAt(j-1)){
                    dp[1][i][j]=dp[1][i][j-1]+dp[0][i-1][j-1];
                }else{
                    dp[1][i][j]=dp[1][i][j-1];
                }
            }
        }

        int result=dp[0][answer.length()][devilBridge.length()]+dp[1][answer.length()][devilBridge.length()];
        System.out.println(result);
    }
}