풀이 방법
먼저 재귀적으로 완전탐색을 이용해서 풀었다. 하지만 시간초과가 나오고 말았다.
그래서 DP를 추가해 주었다.
DP는 [현재 밟은 곳][찾고 있는 문자 인덱스][돌다리 종류] 로 나타내었다.
예제 입력 3번을 예로 들자면
GGGGRRRR GGGGRRRR GGGGRRRR GGGGRRRR
SSSSGGGG SSSSGGGG SSSSGGGG SSSSGGGG
이렇게 찾은 후 다음 G에서
GGGGRRRR GGGGRRRR GGGGRRRR GGGGRRRR
SSSSGGGG SSSSGGGG SSSSGGGG SSSSGGGG
똑같이 반복 될것이다. 그래서 위쪽의 돌다리에서 3번째 G를 밟은 후 현재는 아래쪽의 처음 나오는 G를 밟고 있으면 현재 밟은 곳에서 찾고 있는 문자가 인덱스와 돌다리의 종류가 같은 케이스가 나온적이 있으므로 DP에 저장된 값을 가지고 오는 것이다.
내 코드
package com.company;
import java.io.*;
import java.util.*;
public class Main {
static String angel;
static String devil;
static String str;
static int cnt;
static int[][][] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
str = br.readLine();
devil = br.readLine();
angel = br.readLine();
cnt = 0;
dp = new int[str.length()][devil.length()+1][2];
for (int i = 0; i < dp.length; i++) {
for (int j = 0; j < dp[0].length; j++) {
Arrays.fill(dp[i][j], -1);
}
}
cnt += fff(0, 0, 1);
cnt += fff(0, 0, 0);
System.out.println(cnt);
}
static int fff(int index, int s, int c) {
if (str.length() == s) {
return 1;
}
if (dp[s][index][c] > -1) {
return dp[s][index][c];
}
int total = 0;
if (c == 1) {
for (int i = index; i < devil.length(); i++) {
if (str.charAt(s) == devil.charAt(i)) {
total += fff(i + 1, s + 1, 0);
}
}
} else {
for (int i = index; i < devil.length(); i++) {
if (str.charAt(s) == angel.charAt(i)) {
total += fff(i + 1, s + 1, 1);
}
}
}
return dp[s][index][c] = total;
}
}
'코딩테스트 > [백준] 코딩테스트 연습' 카테고리의 다른 글
크게 만들기 - 2812번 (0) | 2021.10.07 |
---|---|
짐 챙기는 숌 (0) | 2021.10.07 |
괄호 제거 - 2800번 (0) | 2021.10.06 |
듣보잡 - 1764번 (0) | 2021.10.06 |
평범한 배낭 - 12865번 (0) | 2021.10.05 |