[JAVA]백준 12919번: A와 B 2

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

12919번: A와 B 2

1. 문제 설명

 

두 문자열 S, T가 주어졌을 때, S를 T로 바꾸는 게임이다. 문자열을 바꿀 때는 다음과 같은 두 가지 연산만 가능하다.

• 문자열의 뒤에 A를 추가한다.
• 문자열의 뒤에 B를 추가하고 문자열을 뒤집는다.

주어진 조건을 이용해서 S를 T로 만들 수 있으면 1, 없으면 0으로 출력한다.

 

2. 풀이

 

T문자열에서 S문자열로 변경할 때 2가지 경우의 수 (문자열 뒤에 A를 제거하거나, 문자열 앞에 있는 B를 제거하고 문자열을 뒤집는 경우)가 있기에 최대 경우의 수가 2^50(T의 최대 길이)이 나온다고 생각하여 시간 초과를 고려하여 DP를 이용해서 풀었다.

 

그러나 경우의 수를 깊게 생각해보면 항상 2가지의 경우의 수가 생성되지 않기에 dp 없이 풀어도 괜찮을 것 같다.

 

문자열의 경우의 수는 아래와 같이 4가지가 있다.

1. A ~ A
2. A ~ B
3. B ~ A
4. B ~ B

여기서 2가지의 경우의 모두 가능한 것은 3번뿐이다. 따라서 최대 경우의 수가 2^50이 될 수 없다.

 

다만, S문자열에서 T문자열로 재귀함수를 반복한다면 최대 경우의 수는 2^50이 된다. 왜냐하면 T 문자열에서 S문자열로 만들어 가는 과정은 기존의 T문자열의 형식을 고려하지만, S문자열에서 T문자열로 만드는 과정은 현재 S문자열이 어떤 문자열이든 상관없이 2가지의 경우가 모두 가능하기 때문이다.

 

따라서 무조건, T문자열에서 S 문자열로 만들어 가면서 답을 구해야 한다.

 

기본적인 로직은 아래와 같다.

 

left는 문자열의 시작 인덱스 , right는 문자열의 끝 인덱스를 의미한다.

 

1. left를 0, right를 T문자열의 길이로 재귀 함수 makeWord를 시작한다.

2. left 인덱스가 'B'인 경우 문자열을 뒤집고 left 인덱스를 제외한다.

3. right 인덱스가 'A'인 경우 right 인덱스를 제외한다.

 

주의해야 할 점이 있는데 문자열이 뒤집힌다는 점이다.

 

따라서 left> right인 경우(문자열이 뒤집힘) 문자열을 뒤집고 left 인덱스를 제거하려면 left-1, right 인덱스를 제거하려면 right+1을 해야 한다.

left <right인 경우 (문자열이 뒤집히지 않음) 문자열을 뒤집고 left 인덱스를 제거하려면 left+1, right 인덱스를 제거하려면 right-1을 해야 한다.

 

(이해가 잘 안 간다면 손으로 left, right 숫자를 써보면서 2가지 로직을 해보면 쉽게 이해가 갈 것이다.)

 

이 점만 주의해준다면 나머지는 구현만 하면 된다.

 

 

3. 코드

// JAVA 11, 시간 136ms, 메모리 14288KB

import java.io.*;


public class Main {

    public static String input;
    public static String change;
    // 1 : true, 2: false
    public static int[][] dp = new int[51][51];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input = br.readLine();
        change = br.readLine();

        if(makeWord(0,change.length()-1))
            bw.write("1");
        else
            bw.write("0");

        bw.flush();



    }

    // T 문자열에서 S 문자열로 만들어 가는 과정
    public static boolean makeWord(int left, int right){

        int length = Math.abs(right - left) + 1;

        // 길이가 input 길이와 같다면 두 문자열이 같은지 검증
        if (length == input.length()) {
            return isSame(left, right);
        }

        if (dp[left][right] != 0) {
            return dp[left][right] == 1;
        }

        int add = (left < right) ? -1 : 1;


        boolean result=false;

        if(change.charAt(right)=='A'){
            result = makeWord(left, right + add);
        }

        if(change.charAt(left)=='B'){
            result |= makeWord(right, left - add);
        }


        dp[left][right] = result ? 1 : 2;

        return result;

    }

    // 현재 문자열과 input 문자열이 같은지 비교해주는 함수
    public static boolean isSame(int start, int end){
        if (start > end) {
            for(int x=start;x>=end;x--){
                if (change.charAt(x) != input.charAt(start - x)) {
                    return false;
                }
            }

        }else{
            for (int x = start; x <= end; x++) {
                if(change.charAt(x)!=input.charAt(x-start))
                    return false;
            }
        }

        return true;
    }




}