백준 GOLD 5 [12919번] A와 B 2 {언어 : Python} [반례 포함]

문제 링크

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

정답 코드

s = input()
t = input()
lenS = len(s)
lenT = len(t)
answer = 0

def isIncluded(arr):
    normarlString = "".join(arr)
    reversString = "".join(arr[::-1])
    return normarlString in t or reversString in t

def dfs(length, arr):
    global answer
    if answer:
        return

    if length == lenT:
        string = "".join(arr)
        if string == t:
            answer = 1
        return

    if isIncluded(arr+["A"]):
        dfs(length+1, arr+["A"])
    if isIncluded(["B"] + arr[::-1]):
        dfs(length+1, ["B"] + arr[::-1])

dfs(lenS, list(s))
print(answer)

풀이 방법

1. 길이가 lenT와 같아지면 종료되는 재귀함수를 만든다.
2. 만약 이미 바꿀 수 있음을 확인했다면 종료시킨다.
3. 재귀가 최대 2^50 = 1,125,899,906,842,624번 연산이 될 수 있다.
   •  따라서 바꾸려고 하는 문자열이 t에 있는지 확인하고 재귀를 돌린다.
     • 여기서 문자열을 뒤집어서도 확인 해봐야 한다.
     • 그렇지 않으면 다음과 같은 반례가 나온다.
     • s = AB
     • t = BABB
     • 답 = 1
     • 오답 = 0
4. 연산이 끝나면 answer를 출력한다

느낀점

• 항상 반례가 있다는 점을 명심하자.