백준 7490 0만들기(python)

1. 0 만들기

이 문제는 재귀함수를 이용하여 트리형태로 확산되는 모든 경우를 확인하는 방법으로 풀 수 있다. 단순히 순차적으로 탐색하는 것이 아니라, 하나의 경우에서 여러개의 경우로 파생되는 형태에서는 반복문을 사용하기 힘들기 때문에 이런 문제들을 해결하기 위해 재귀함수 사용에 익숙해질 필요가 있다.

문제

1부터 N까지의 수를 오름차순으로 쓴 수열 1 2 3 ... N을 생각하자.
그리고 '+'나 '-', 또는 ' '(공백)을 숫자 사이에 삽입하자(+는 더하기, -는 빼기, 공백은 숫자를 이어 붙이는 것을 뜻한다). 이렇게 만든 수식의 값을 계산하고 그 결과가 0이 될 수 있는지를 살피자.
N이 주어졌을 때 수식의 결과가 0이 되는 모든 수식을 찾는 프로그램을 작성하라.

입력

첫 번째 줄에 테스트 케이스의 개수가 주어진다(<10).
각 테스트 케이스엔 자연수 N이 주어진다(3 <= N <= 9).

출력

각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다.

2. 문제 해석

이 문제에는 특별한 규칙성을 찾기 힘들기 때문에 모든 경우의 수를 연산해야 한다.
아래의 그림과 같이 각각의 상황에서 3가지로 경우가 갈라진다.

3. 문제 풀이

1) 모든 연산자 조합을 만든 후 숫자와 결합(eval() 사용)

recur 라는 함수를 정의하고 arr 배열에 각각의 연산자를 넣은 뒤 recur 함수를 호출하고 다시 원소를 뺀다. 그 후 다른 연산자에 대해 이것을 반복한다.
배열의 길이가 입력한 값에 도달하면, 연산자 조합을 모은 배열에 담는다. 이 때 배열을 복사해서 담아야만 한다. 그 이유는 arr.pop()을 하여 연산자를 빼낼 때, 이미 연산자 조합을 담은 배열에 담긴 내용 또한 동시에 수정되기 때문이다. 만약에 복사를 하지 않고 넣는다면 연산자 조합에는 빈배열만 조합의 갯수만큼 생성될 것이다.

이후에는 숫자와 연산자를 조합하고 eval 함수를 사용하여 해당 연산이 0인지 확인한 후 0이라면 출력하여 끝낸다.

import copy

def recur(arr, m):
  if len(arr)==m:
    operators.append(copy.deepcopy(arr))
    return
  
  arr.append(' ')
  recur(arr, m)
  arr.pop()
  
  arr.append('+')
  recur(arr, m)
  arr.pop()

  arr.append('-')
  recur(arr, m)
  arr.pop()

n = int(input())

for _ in range(n):
  operators = []
  m = int(input())
  recur([], m-1)
  # print(operators)

  for operator in operators:
    statement = ''
    for i in range(m-1):
      statement+= str(i+1)+operator[i]
    statement+=str(m)
    if (eval(statement.replace(' ', '')))==0:
      print(statement)
  print()

eval 이라는 함수는 문자열로 작성된 코드 내용을 그대로 실행시켜준다. 예를 들어

a = eval('1+2')
print(a) // 3

// 심지어 아래의 코드도 실행가능하다.
eval('print(1+2)') // 3

2) eval()을 사용하지 않고 풀기

eval 함수가 없는 c++ 같은 언어에서는 이 문제를 어떤 방식으로 푸는지 궁금했다. 다른 사람이 c++ 풀이를 파이썬으로 그대로 배껴보았다. 풀이를 그대로 이해하는 데에도 시간이 꽤 걸렸다. 초보자들에게 python으로 코딩테스트를 준비하라고 하는 이유를 바로 이해하게 되었다...
재귀함수를 사용하며, 매개변수로는 아래의 값들이 들어간다.
sum   : 현재까지의 연산값
sign   : 다음 연산에 num과 함께 들어갈 연산자(+는 1로, -는 -1로 표현, 빈칸이 들어갈떄는 무의미함)
num   : 다음에 연산될 숫자
n         : 몇번째 항인지를 나타냄
string : 현재까지의 표현식

def recur(sum, sign, num, n, string):
  if (n == N):
    sum = sum + (sign*num)
    if sum == 0:
      print(string)
  else:
    recur(sum         ,sign , num*10+(n+1), n+1, string+' '+str(n+1))
    recur(sum+sign*num,1    , (n+1)       , n+1, string+'+'+str(n+1))
    recur(sum+sign*num,-1   , (n+1)       , n+1, string+'-'+str(n+1))
      
test_case = int(input())

for _ in range(test_case):
  N = int(input())
  recur(0,1,1,1,"1")
  print()