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

30 Aug 2023 in Algorithm on 다이나믹 프로그래밍

https://www.acmicpc.net/problem/2602

풀이

길이 두개가 있고, 두 길의 발판을 번갈아가며 밟으면서 길을 건너야 한다.

밟아야 할 발판의 종류는 정해져 있다.

완전탐색하면 시간초과가 날 것이고, dp를 사용해야 한다.

건너기 위해 밟아야 할 발판을 route라하고, 길을 a와 b라고 하면,

dp배열을 [2][route][a,b]로 만들 수 있다.

지금 밟아야 할 발판과 현재 보고 있는 길의 발판이 같으면

dp[현재 길][i][j] = dp[현재 길][i][j-1] + dp[다른 길][i-1][j-1]이 된다.

발판이 다르면 같은 길에서 바로 전에꺼를 가져오면 된다.

즉, dp[현재 길][i][j] = dp[현재 길][i][j-1]이 된다.

끝까지 진행하여 dp[a]의 끝값과 dp[b]의 끝값을 더해준다.

---

메모리: 14120KB

시간: 120ms

언어: Java 11

코드

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String route = br.readLine();
        String a = br.readLine();
        String b = br.readLine();

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

        for (int i = 1; i < route.length() + 1; i++) {
            for (int j = 1; j < a.length() + 1; j++) {
                if (route.charAt(i - 1) == a.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 (route.charAt(i - 1) == b.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 ans = dp[0][route.length()][a.length()] + dp[1][route.length()][a.length()];

        System.out.println(ans);
    }

}