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

1. 문제

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

7490번: 0 만들기

문제 유형: 재귀 함수

 

• 1부터 n까지의 수열을 만든 후 총 $3^{n-1}$개의 가능한 연산자 리스트를 재귀 함수로 구현
  • 최대 n은 9이므로 완전 탐색을 이용해도 상관 없음
• 수와 연산자 리스트를 이용하여 string으로 수식을 나타냄
• eval() 함수를 이용하여 string 형태의 수식을 계산
• 계산값이 0일 경우 해당 수식을 출력

2. 소스코드

import sys
import copy


def operator(list, n):
    if len(list) == n:
        operator_list.append(copy.deepcopy(list))
        return
    list.append(' ')
    operator(list, n)
    list.pop()

    list.append('+')
    operator(list, n)
    list.pop()

    list.append('-')
    operator(list, n)
    list.pop()


test = int(sys.stdin.readline())

for _ in range(test):
    operator_list = []
    n = int(sys.stdin.readline())
    operator([], n - 1)

    nums = [i for i in range(1, n + 1)]

    for operators in operator_list:
        string = ''
        for i in range(n - 1):
            string += str(nums[i]) + operators[i]
        string += str(nums[-1])
        if eval(string.replace(' ', '')) == 0:
            print(string)
    print()