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

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

7490번: 0 만들기

문제

1부터 N까지의 수를 오름차순으로 쓴 수열 1 2 3 ... N을 생각하자.

그리고 '+'나 '-', 또는 ' '(공백)을 숫자 사이에 삽입하자(+는 더하기, -는 빼기, 공백은 숫자를 이어 붙이는 것을 뜻한다). 이렇게 만든 수식의 값을 계산하고 그 결과가 0이 될 수 있는지를 살피자.

N이 주어졌을 때 수식의 결과가 0이 되는 모든 수식을 찾는 프로그램을 작성하라.

입력

첫 번째 줄에 테스트 케이스의 개수가 주어진다(<10).

각 테스트 케이스엔 자연수 N이 주어진다(3 <= N <= 9).

출력

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

예제 입력 1 복사

2
3
7

예제 출력 1 복사

1+2-3

1+2-3+4-5-6+7
1+2-3-4+5+6-7
1-2 3+4+5+6+7
1-2 3-4 5+6 7
1-2+3+4-5+6-7
1-2-3-4-5+6+7

 

import copy
# 모든 오퍼레이터 리스트의 경우의 수를 찾음
def recursive(arr,n):
    if len(arr)==n:
        operators_list.append(copy.deepcopy(arr)) # 카피를 이용해야지 다른 연산에 영향안받음
        return
    arr.append(' ')
    recursive(arr,n)
    arr.pop() # 재귀를 위해 다시 빼기
    
    arr.append('+')
    recursive(arr,n)
    arr.pop()
    
    arr.append('-')
    recursive(arr,n)
    arr.pop()
    
t=int(input())
for _ in range(t):
    operators_list=[]
    n=int(input()) # 숫자의 개수
    recursive([],n-1) # 연산의 개수는 숫자-1이므로 n-1
    integers=[i for i in range(1,n+1)] # 숫자 배열 생성
    for operators in operators_list: # 모든 연산 리스트에 대해서 계산
        string=''
        for i in range(n-1):
            string+=str(integers[i])+operators[i]
        string+=str(integers[-1])
        # eval: 스트링으로 입력된 수식을 계산해줌
        if eval(string.replace(' ',''))==0:
            print(string)
    print()