백준 12919번: A와 B 2

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

문제 풀이

재귀

문자열 T를 S로 만들 수 있는지 판단하기 위해서 재귀 함수 solve를 이용해 S와 같은 길이가 될때까지 맨 뒤에 A가 있다면 맨 뒤 A를 제거하고 맨 앞에 B가 있다면 B를 제거하고 문자열을 뒤집는다.

이 과정을 통해 T를 S의 길이만큼 줄인 문자열이 S가 될 수 있으면 1, 아니면 0을 출력하면 정답

풀이 설명

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

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

주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 프로그램을 작성하시오.

첫 번째 연산을 하면 문자열의 마지막에 A가 오게되고, 두 번째 연산을 하면 문자열의 맨 앞에 B가 오게 된다. 즉 두 연산의 결과로 확정되는 문자가 맨 앞과 맨 뒤로 둘이 다르기 때문에 결과 문자열로 항상 어떤 연산을 할 수 있는지 바로 알 수는 없다.

따라서 직접 어떤 연산을 했는지 해보는 수밖에 없는데, 직접 연산을 해 문자열을 만드려면 모든 경우를 확인해야 하지만 역으로 T를 S로 만들도록 연산을 한다면 문자열의 맨 앞에 B가 있는 경우와 맨 뒤의 A가 있는 경우만 연산을 하면 되기 때문에 연산 횟수가 많이 줄어들게 된다.

하지만 T를 S로 만드는 과정 중 문자열이 맨 앞이 B이고 동시에 맨 뒤가 A일 수 있기 때문에 이 경우 어떤 연산을 하는지에 따라 문자열이 달라지게 된다. 따라서 두 경우를 모두 확인해야 하기 때문에 재귀 함수를 이용해 두 경우 모두 확인하면 된다.

따라서 재귀 함수 solve에 들어간 문자열의 길이를 S의 길이와 비교해 같으면 문자열 S와 같은지 비교해 가능한지를 answer에 저장하고, 같지 않다면 맨 뒤 문자가 A라면 맨 뒤 문자를 지운 문자열을 solve에 전달해 다시 호출하고, 맨 앞 문자가 B라면 맨 앞 문자를 지운 뒤 뒤집은 문자열을 solve에 전달해 다시 호출한다.

이 과정을 통하면 두 연산을 역으로 이용해 T를 S의 길이만큼 줄인 문자열을 모두 확인할 수 있고 이 과정에서 정확히 S가 되는 문자열을 찾으면 그 연산의 반대로 하면 S를 T로 만들 수 있는 것이므로 1을 출력하면 되고, 없다면 0을 출력하면 정답이 된다.

소스 코드

var S = ""
var T = ""
var answer = false

fun main(){
    val br = System.`in`.bufferedReader()
    S = br.readLine()
    T = br.readLine()
    solve(T)
    println("${if(answer) 1 else 0}")
}

fun solve(s: String){
    if(s.length == S.length){
        if(s == S){
            answer = true
        }
        return
    }
    if(s.last() == 'A'){
        solve(s.dropLast(1))
    }

    if(s.first() == 'B'){
        solve(s.drop(1).reversed())
    }
}