[n12919] A와 B 2 in python

---

[처음 한 생각]

s를 t로 바꾸기 위해 2가지 연산만 사용할 수 있다.

그러면 역으로 생각해서 t를 s로 바꿀 수 있으면 그게 답이 아닐까 생각했다.

s : A

t : BABA이면,

 

BABA에서 맨 오른쪽에 있는 A는 빼내고,

B는 거꾸로 한 뒤 B를 빼내고,

BA에서 A를 빼내고,

B가 남는다..?

 

근데 예제는 분명 s에서 t로 바꿀 수 있다고 했는데..

 

이게 아닌가보다..

 

아니다..

마지막 부분이 잘못된 오류가 있었다!

 

BA에서 1번 연산이 아닌 2번 연산을 취하면 된다.

그럼 A가 남게 되니까

최종값은 1이 된다..!

---

[풀이]

 T->S 과정을 거치면 답을 구할 수 있다.

 

S->T로 만들면서 나타날 수 있는 경우의 수는 총 4가지

 

1번 연산 : 맨 끝에 A 추가

2번 연산 : 맨 끝에 B추가 후 문자열 뒤집기

 

1. A.....A

맨앞과 끝이 A

> 이런 경우엔 A로 시작하는 문자열에 1번 연산을 해주면 나올 수 있는 방법

 

2. A.....B

맨앞이 A, 맨 끝이 B

> 아무리 연산을 해봐도 도저히 나올 수 없는 경우

 

3. B......A

맨 앞이 B, 맨 끝이 A

> 2가지의 연산을 사용할 수 있다.

1번 연산을 사용할 수도 있고, 2번 연산을 사용할 수도 있다.

 

4. B......B

맨 앞이 B, 맨 끝이 b

> 2번 연산을 수행하면 된다.

 

t[0]=='B' , t[-1]=='A'로 정한 이유는?

1번 연산을 사용하는 경우의 수는 A....A, B...A >> t[-1]=='A'

2번 연산을 사용하는 경우의 수는 B....A,B....B니까! >> t[0]=='B'

 

 

 

BABA - 1번 연산 - BAB - 1번 연산 - B - 오답

                                        2번 연산 - AB - A - 정답

2번 연산 - ABAB - 1번 연산 - AB - 오답

s = list(input())
t = list(input())


def find(t):
    if len(t) == len(s):
        return t == s

    if t[0] == 'B' and find(t[:0:-1]):
        return True
    if t[-1] == 'A' and find(t[:-1]):
        return True


print(1 if find(t) else 0)

s와 t의 길이가 같고, s와 t가 같은 문자열이면 True를 , 다른 문자열이면 False를 반환한다.

맨앞 문자열이 B이고 뒤집고 B제거한 문자열을 find()함수에 넣고 돌린다. 

만약 둘다 True이면, 즉 t와 s가 같아지면, 그땐 True 반환

맨끝 문자열이 A이고, A제거한 문자열을 마찬가지로 find()함수에 넣고 돌린다.

이때 t와 s가 같아지면 True 반환, 아니면 False반환

 

 

s = list(input())
t = list(input())

button = False

def find(t):
    if len(t) == len(s):
        if t == s:
            button=True
        return

    if t[0] == 'B':
        t = t[::-1]
        t.pop()
        find(t)
        t.append('B')
        t = t[::-1]
    if t[-1] == 'A':
        t.pop()
        find(t)
        t.append('A')


find(t)

if button:
    print(1)
else:
    print(0)

 

 

 

참고 출처

https://dirmathfl.tistory.com/229

백준: 12919 A와 B 2