2602. 돌다리 건너기

가능한 from, to 돌다리 개수를 저장하며 나아가는 로직

마법의 두루마리에 적힌 문자열의 순서대로 

chatAt(from) charAt(to)가 일치하면 저장하며 나아갑니다.

대신, 마법의 두루마리에 적힌 문자열의 길이가 1인 경우 해당 로직을 수행하지 못하므로

따로 로직을 수행합니다.

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Q2602 { static int[][][] dp; public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); String resultStr = " " + st.nextToken(); st = new StringTokenizer(br.readLine()); String goodLoad = st.nextToken(); st = new StringTokenizer(br.readLine()); String badLoad = st.nextToken(); dp = new int[resultStr.length()][badLoad.length()][goodLoad.length()]; if (resultStr.length() == 2) { char tempChar = resultStr.charAt(1); int result = 0; for (int i = 0; i < badLoad.length(); i++) { if (badLoad.charAt(i) == tempChar) { result++; } } for (int j = 0; j < goodLoad.length(); j++) { if (goodLoad.charAt(j) == tempChar) { result++; } } System.out.println(result); return; } for (int k = 1; k < resultStr.length()-1; k++) { for (int j = 0; j < badLoad.length(); j++) { char tempBadChar = badLoad.charAt(j); if (resultStr.charAt(k) == tempBadChar) { int temp = 0; if (k == 1) { temp = 1; } else { for (int i = 0; i < j; i++) { temp += dp[k-1][j][i]; } } for (int i = j+1; i < goodLoad.length(); i++) { char tempGoodChar = goodLoad.charAt(i); if (resultStr.charAt(k+1) == tempGoodChar) { dp[k][j][i] = temp; } } } } for (int i = 0; i < goodLoad.length(); i++) { char tempGoodChar = goodLoad.charAt(i); if (resultStr.charAt(k) == tempGoodChar) { int temp = 0; if (k == 1) { temp = 1; } else { for (int j = 0; j < i; j++) { temp += dp[k-1][j][i]; } } for (int j = i+1; j < badLoad.length(); j++) { char tempBadChar = badLoad.charAt(j); if (resultStr.charAt(k+1) == tempBadChar) { dp[k][j][i] = temp; } } } } } int result = 0; for (int i = 0; i < goodLoad.length(); i++) { for (int j = 0; j < badLoad.length(); j++) { result += dp[resultStr.length()-2][i][j]; } } System.out.println(result); } }