[백준-7490] 0만들기 파이썬

# 문제

# 풀이

다음과 같이 1 다음에 공백,'+','-'가 오고 2 다음에도 똑같이 반복할 수 있다. 재귀적으로 하나씩 스택이 쌓이면서 해결해 나가는 방법을 사용하면 될 듯했다. 어떻게 보면 재귀를 이용해 완전 탐색하는 방법이고, 최종 결과가 0이면 출력해주면 된다.

##실패했지만 해결의 실마리를 준 풀이

def zero2(start,n,result,end):
  if start == n:
    if result == 0:
      return print(end)
    return
  next = start+1

  str_plus = end + "+" + str(next)
  zero(next,n,result+next,str_plus)

  str_minus = end + "-" + str(next)
  zero(next,n,result-next,str_minus)

# 여기서 틀려져버림ㅠㅠ
  str_empty = end + " " + str(next)
  zero(next,n,start*10+next,str_empty)

처음에는 위와 같이 문제를 풀었다. end로는 "1 + 2 3 - 4 ... " 와 같이 출력하기 위한 문자열을 계속해서 더해줬다. 위 코드는 +와 -까지는 잘 수행 되는데, empty가 왔을때 즉 수를 이어줄때 문제가 생긴다. 수를 이어주게 되면 3가지의 경우가 존재 할 수 있다. 앞에 수가 +,-,공백인데, 위 풀이는 result로 계속해서 넘겨주기 때문에 앞에가 +인지 -인지를 구분짓지 못해버린다. 그러나 여기서 답을 알 수 있었다. 넘겨주는 string은 잘 넘어가는 것을 알 수 있다. 그러면 파이썬 eval를 사용하면 되지 않나?!

 

## 성공한 풀이

def zero(target,n,text):
  if target == n :
    if eval(text.replace(" ","")) == 0 :
      return print(text)
    return

  next = target+1
  # empty
  str_empty = text + " " + str(next)
  zero(target+1,n,str_empty)

  # plus
  str_plus = text + "+" + str(next)
  zero(target+1,n,str_plus)

  # minus
  str_minus = text + "-" + str(next)
  zero(target+1,n,str_minus)

def solve():
  case = int(input())
  for _ in range(case):
    N = int(input())
    zero(1,N,"1")
    print()


if __name__ == '__main__':
    solve()

문자열을 계속해서 더해나가면서 주어진 수까지의 입력이 끝나면 eval을 이용해서 0인지 확인하고 맞다면 바로 출력해버리면 된다.

처음에는 문자열이 " " 이렇게 공백을 포함해버리니까 eval이 먹지 않았는데 replace를 활용해서 " " 공백 문자열을 빈 문자열로 바꾼다음에 계산해주면 됐다. 

 

# 마치며

출력 형식이 잘못됐습니다.. 중간에 반복문 사이에 print()를 넣어 줘야 했었다