경이로운 그리디 알고리즘4 -역으로 생각해서 경우의 수를 줄이는 테크닉-

1. 문제

 

12904번: A와 B (acmicpc.net)

12904번: A와 B

 

2. 풀이

 

S에서 T를 만들려고만 한다면 이 문제가 상당히 어렵다

 

그냥 왠지 모르지만 어떤 문제든 역으로 시도해볼때 뭔가 보일수도 있다

 

조금 생각해보면

 

1) 문자열의 뒤에 A를 추가한다

 

2) 문자열을 뒤집고 뒤에 B를 추가한다

 

두 연산만으로 S에서 T가 만들어졌는데 문자열 T가 ABBA인 경우를 생각해보자.

 

ABBA는 이전에 어떤 문자열이었을까?

 

오직 1가지인 ABB인 경우만 ABBA로 될 수 있다.

 

어떤 문자열에서 2가지 연산 중 하나를 사용해서, ABBA로 되어야하는데 

 

2) 연산을 사용했다면 문자열을 뒤집고 마지막에 B를 추가하니까 ???B로 되니까 불가능하다.

 

하지만 1) 연산을 사용한다면 ???A로 되고 ABBA가 될 수 있으니 가능하다.

 

비슷한 방식으로 ABB는 이전에 어떤 문자열이었는지 추측할 수 있을까?

 

마지막에 B를 추가하는 2) 연산을 사용해서 ABB가 되었을 것이다.

 

AB > ABB가 되었을 것인데, AB가 되기 전에 문자열을 뒤집는 과정이 있었으니, 

 

BA > AB > ABB가 되었을 것이다. 즉, BA가 ABB로 2) 연산에 의해 바뀌었다.

 

그러면 비슷한 논리로 BA는? 1) 연산을 사용해서 B에서 BA가되었을 것이다.

 

그러므로, B > AB > ABB > ABBA가 가능하다.

 

S에서 T로 가는지 확인해볼려면, 셀수없이 많은 경우를 생각해서 T가 되는지 검사해봐야하지만

 

T에서 S로 가는지 생각해본다면, 놀랍게도 오직 1가지만 가능하다

 

그거는 현재 문자열의 마지막 문자가 A인지 B인지 추측해서,

 

A라면 A를 제거하면 되고, B라면 B를 제거하고 뒤집으면 된다.

 

 

 

따라서 T에서 시작해서 마지막 문자가 A라면 A를 제거하고

 

B라면 B를 제거하고 뒤집어본다.

 

S와 길이가 같을때까지 위 과정을 반복하고, 길이가 같다면 S와 같은 문자열인지 체크한다.

 

같다면 S에서 T로 가능하고, 같지 않다면 S에서 T로 불가능하다.

 

from sys import stdin

s = list(stdin.readline().rstrip())
t = list(stdin.readline().rstrip())

a = len(s)
b = len(t)

answer = 0

while b != a:
    
    #마지막 문자가 A라면, A를 제거
    if t[-1] == 'A':
        
        t.pop()
        b -= 1
    
    #마지막 문자가 B라면 B를 제거하고 뒤집어준다.
    else:
        
        t.pop()
        b -= 1
        t = t[::-1]
    
    #길이가 서로 같아진다면 두 문자열이 같은지를 체크해본다.
    if a == b:
        
        if t == s:
            
            answer = 1
        
        else:
            
            answer = 0
        break

print(answer)

 

 

3. 문제2

 

12919번: A와 B 2 (acmicpc.net)

12919번: A와 B 2

 

4. 풀이

 

똑같은 문제인데.. 연산이 다르다.

 

1) 뒤에 A를 추가

 

2) 뒤에 B를 추가하고 문자열을 뒤집기

 

첫번째 문제와 비슷하게 역으로 생각해보았는데.. 이전 문제와는 다르게 오직 1가지 경우만 가능하지는 않다.

 

마지막 문자가 A라고 해서 1번 연산을 사용했다는 보장이 없고 2번 연산도 가능하거든

 

그래서 그냥 S에서 T로 순방향으로 브루트 포스를 사용해서 완전탐색을 수행해봄

 

문제 제한이 S랑 T가 길이가 50까지다 보니... 2초면 할만하지 않을까 생각했다 이거지

 

from sys import stdin

def search(s,t,b):
    
    if len(s) == b:

        if s == t:

            return 1

        else:

            return 0

    else:
        
        s.append('A')
        s1 = ''.join(s)
        s.pop()
        s.append('B')
        s2 = ''.join(s)
        s2 = s2[::-1]

        return max(search(list(s1),t,b),search(list(s2),t,b))

s = list(stdin.readline().rstrip())
t = list(stdin.readline().rstrip())

b = len(t)

print(search(s,t,b))

 

근데 어림없더라... 재귀라 그런지 S가 1이고 T가 50이면 경우의수가 상당히 많긴할듯

 

거꾸로 생각하면 시간안에 통과할 수 있다고 하길래 다시 한번 차분하게 거꾸로 생각해봄

 

T에서 S로 만들건데..

 

마지막 문자가 A라면? 2가지가 가능하다.

 

1) 이전 문자열에서 뒤에 A를 추가했다.

 

2) 이전 문자열의 첫번째 문자가 A인 경우, A?????에서 B를 추가하고

 

A?????B에서 문자열을 뒤집어 B?????A로 만들었다.

 

마지막 문자가 B라면? 오직 1가지만 가능하다.

 

1) 이전 문자열의 첫번째 문자가 B인 경우, B?????에서 B를 추가하고

 

B?????B에서 문자열을 뒤집어 B?????B를 만들었다.

 

S에서 T로 완전탐색을 하면, 아무 생각없이 모든 경우를 생각해서 탐색하는데,

 

T에서 S로 탐색을 하면, 위와 같이 3가지 경우만 탐색할 수 있게 된다.

 

from sys import stdin

def search(s,t,a,b):
    
    if a == b:

        if s == t:

            return 1

        else:

            return 0

    else:
        
        #마지막 문자가 A인 경우, 1)연산, 2)연산 가능
        if t[-1] == 'A':
                
            return max(search(s,t[:-1],a,b-1),search(s,t[::-1][:-1],a,b-1))
        
        #마지막 문자가 B인 경우,
        #오직 1가지 2)연산만 가능
        else:
                
            return search(s,t[::-1][:-1],a,b-1)
                       
s = stdin.readline().rstrip()
t = stdin.readline().rstrip()

a = len(s)
b = len(t)

print(search(s,t,a,b))

 

근데 이래도 시간초과가 나더라고..?

 

경우를 나누긴 했지만 결국 많은 재귀 경로를 탐색하다보니 완전탐색 하는거랑 마찬가지네..

 

T의 0번째 문자가 A인가 B인가로 나눠 생각해보자.

 

0번째 문자가 B라면...?

 

1) 마지막 문자가 B인 경우

 

B????B 형태인데 오직 2) 연산만 가능하다.

 

문자열을 뒤집고, 마지막 문자 B를 제거한다.

 

2) 마지막 문자가 A인 경우

 

B????A 형태인데, 1), 2) 모두 가능하다.

 

이전 문자열이 A를 제거해서 B????이거나,

 

뒤집어서 A????B로 만들고 B를 제거한 A????이거나..

 

-------------------------------------------------------

 

반대로 0번째 문자가 A인 경우?

 

1) 마지막 문자가 B라면?

 

A????B 형태인데... 이러한 문자열로 만들 수 있나?

 

먼저 1) 연산은 불가능하지.. 뒤에 A를 추가하는 연산인데 B가 있으니까

 

그러면 2) 연산을 썼다는 의미인데.. 먼저 뒤집고 B????A 형태인데 B를 추가할려면 마지막이 B여야하는데 

 

지금 A라서 B를 추가한 것도 아니네

 

즉 T 문자열이 0번째 문자가 A인데 마지막 문자가 B인 경우는 S에서 무슨 짓을 하더라도 T로 만들 수 없다.

 

그러니까 더 이상 재귀 경로를 탐색할 필요가 없이 바로 0을 return해서 끊어버리는게 중요하다

 

2) 마지막 문자가 A라면?

 

A????A 형태인데 오직 1) 연산만 가능하겠지..

 

이를 재귀로 구현하면 시간안에 통과가능

 

불가능한 경우를 백트래킹으로 끊어버린게 유효했다.

 

from sys import stdin

def search(s,t,a,b):
    
    #두 문자열의 길이가 같을때, 두 문자열이 서로 같은지 비교
    if a == b:

        if s == t:

            return 1

        else:

            return 0
    
    #두 문자열의 길이가 다르다면,
    else:
        
        #T의 0번째 문자가 B인 경우,
        if t[0] == 'B':
            
            #마지막 문자도 B라면 이전에 2)연산을 사용했다.
            #T를 뒤집고, 마지막 문자 B를 제거한다.
            if t[-1] == 'B':
                
                return search(s,t[::-1][:-1],a,b-1)
            
            #마지막 문자가 B가 아니라면? 1),2) 모두 가능하다.
            else:
                
                return max(search(s,t[:-1],a,b-1),search(s,t[::-1][:-1],a,b-1))
        #T의 0번째 문자가 A인 경우
        else:
            
            #T의 마지막 문자가 B라면?
            #S에서 1),2) 연산을 사용해서 절대로 만들 수 없다
            #백트래킹으로 재귀 탐색 중지
            if t[-1] == 'B':
                
                return 0
            
            #T의 마지막 문자가 A라면?
            #오직 1)연산만 가능하다.
            else:
                
                return search(s,t[:-1],a,b-1)
                       
s = stdin.readline().rstrip()
t = stdin.readline().rstrip()

a = len(s)
b = len(t)

print(search(s,t,a,b))

 

놀랍긴하네...