[알고리즘] 백준7490 0만들기 - 파이썬

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

7490번: 0 만들기

 

 

[풀이 코드]

import copy

def recurcive(array, n):
    if len(array) == n:
        operators_list.append(copy.deepcopy(array))
        return

    array.append(' ')
    recurcive(array, n)
    array.pop()

    array.append('+')
    recurcive(array, n)
    array.pop()

    array.append('-')
    recurcive(array, n)
    array.pop()

t = int(input())
for _ in range(t):
    n = int(input())
    operators_list = []
    recurcive([], n - 1)
    integer = [i for i in range(1, n+1)]

    for operator in operators_list:
        string = ""
        for i in range(n-1):
            string += str(integer[i]) + operator[i]
        string += str(integer[-1])
        if eval(string.replace(" ", "")) == 0:
            print(string)
    print()

- recurcive() 함수 설명 : 재귀를 통해 +, -, ' ' 세 가지의 부호가 숫자 사이에 들어갈 수 있는 경우의 수를 모두 배열로 만들어줘야 한다. 꼭 deepcopy(깊은 복사)를 사용해야 한다!

 

- 1부터 n까지의 숫자가 담겨있는 integer배열과 부호의 모든 경우를 담은 operators_list배열을 통해 모든 수식을 만들어가면서 수식의 합이 0이 되면 출력해주면 된다. 

 

- eval() 함수를 활용해서 string의 합을 구해줄 때 공백은 숫자와 숫자를 이어주는 것이기 때문에  " "(공백)을 ""(띄어쓰기 없는 공백)으로 교체해줘야 한다.