12919 - A와 B 2 (Java)

 

---

 

문제

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

 

 

풀이

이 문제는 S를 T로 만들려고 하지 말고

 

T를 S로 만든다는 목표로 하면 풀 수 있다. 그러니까 연산을 역으로 해서 S로 갈 수 있는지 확인하는 것이다.

 

이유는, S에서 T로 만들 경우에는 두 연산 모든 경우의 수를 구현해봐야한다.

그러나 이미 만들어진 문자열은 연산을 제한할 수 있다.

 

연산1 : 문자열의 뒤에 A를 추가한다.

연산2 : 문자열의 뒤에 B를 추가하고 문자열을 뒤집는다.

 

위와 같이 있을 때

• 문자열의 첫번째가 B 라면 연산2를 사용해서 만들었을 수 있다.
• 문자열의 끝이 A 라면 연산1을 사용해서 만들었을 수 있다.

 

이렇게 조건을 준다면 경우의 수는 훨씬 줄어든다.

예로,

 

AAA 는 연산 1만 사용해서 만들 수 있다.

BAB 는 연산 2만 사용해서 만들 수 있다.

 

 

단, BA 와 같이 두 연산 모두 수행해봐야 하는 경우가 있다.

그렇기에 재귀로 구현해서 두 경우의 수를 모두 수행할 수 있도록 구성해야한다.

 

코드

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

public class Main {

    public static boolean isPossible = false;
    public static StringBuffer currentString;

    public void process(StringBuffer targetString) {
        if(isPossible) return;
        if(targetString.length() < currentString.length()) return;
        if(targetString.toString().equals(currentString.toString())){
            isPossible = true;
            return;
        }

        if(targetString.charAt(0) == 'B') {
            StringBuffer temp = new StringBuffer(targetString.toString());
            temp.reverse();
            temp.deleteCharAt(temp.length()-1);
            process(temp);
        }
        if(targetString.charAt(targetString.length()-1) == 'A') {
            StringBuffer temp = new StringBuffer(targetString.toString());
            temp.deleteCharAt(temp.length()-1);
            process(temp);
        }
    }

    public void solution() throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        currentString = new StringBuffer(br.readLine());

        process(new StringBuffer(br.readLine()));

        if(isPossible){
            System.out.println(1);
            return;
        }

        System.out.println(0);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }


}

 

후기

 

경우의 수는 거꾸로 로꾸꺼.. 접근 하는걸 잊지말자