[백준] 12919. A와 B 2 (Python)

📌 12919. A와 B 2

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

풀이 과정

처음에는 간단하게 s에 조건1 또는 조건2를 적용해가면서, t와 같아지면 answer을 1로 바꾸는 형식으로 코드를 작성하였다.

s = input()
t = input()

answer = 0
def adding(str1, target):
  global answer
  if target == str1:
    answer = 1
  if len(str1) > len(target):
    return
  adding(str1 + 'A', target)
  str1 += 'B'
  str1 = list(str1)
  str1.reverse()
  str1 = "".join(str1)
  #print(str1)
  adding(str1, target)

adding(s, t)
print(answer)

예제는 알맞게 나왔지만 11%에서 계속 시간초과가 걸렸다. 질문게시판을 보니, 시간초과를 걸리지 않게 하려면, t에서 하나씩 빼면서 s와 같아지는지 확인을 해야 했다. 즉 내가 했던 방식의 반대로 해야했다. 내가 하는 방식은 A혹은 B 추가 2가지 방법을 계속 반복해야 하기 때문에 2의 제곱 형태로 기하급수적으로 경우의 수가 늘어난다. 그렇기 때문에 시간초과가 걸리는 것이다.

💯 정답

s = input()
t = input()

answer = 0
def sub(str1, target):
  global answer
  if len(str1) == len(target):
    if target == str1:
      answer = 1
    return
  if target[-1] == 'A':
    sub(str1, target[:-1])
  if target[0] == 'B':
    #target = target
    sub(str1, target[:0:-1])

sub(s, t)
print(answer)

✍ 끄적끄적

만약 처음에 이문제를 보고 푼다면, 당연히 문제의 흐름에 맞게 s를 t로 바꾸는 식으로 했을 것이다. 하지만, 시간초과가 나왔으니 다른 풀이법을 고안해야하는데, 이때 '거꾸로' 하는 방법도 생각을 해보자. 자꾸 하다보면, 실전 코테에서도 처음부터 거꾸로의 방법을 생각해 낼 수 있을 것이다.