[백준] 7490번 : 0 만들기 ☆

유형 : 재귀

[예제]

2
3
7

[출력]

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

---

1. 풀이

** 핵심 아이디어
1. 자연수 N의 범위(3≤N≤9)가 매우 한정적이므로 완전 탐색으로 문제 해결 가능
2. 수의 리스트와 연산자 리스트를 분리하여 모든 경우의 수 계산
3. 가능한 모든 경우를 고려하여 연산자 리스트를 만드는 것이 관건(재귀 함수 이용)

ex. N = 3
[[' ', ' '], [' ', '+'], [' ', '-'], ['+', ' '], ['+', '+'], ['+', '-'], ['-', ' '], ['-', '+'], ['-', '-']]

4. 파이썬의 eval() 함수를 이용해 문자열 형태의 표현식을 계산

 

import copy

def recursive(array, n):
    if len(array) == n:
        operators_list.append(copy.deepcopy(array))
        return
    
    # 연산자 모든 경우 고려
    array.append(' ')
    recursive(array,n)
    array.pop()
    
    array.append('+')
    recursive(array,n)
    array.pop()
    
    array.append('-')
    recursive(array,n)
    array.pop()
    
 test_case = int(input())
 
 for _ in range(test_case):
    operators_list = []
    n = int(input())
    recursive([],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])
        
        if eval(string.replace(" ","")) == 0:
            print(string)
        
    print()

▷ 연산자 리스트는 3^(n-1)의 공간을 차지하는데 이는 최대 30000정도이기 때문에 모든 경우의 수를 고려해도 된다.

▷ 재귀 함수로 모든 경우를 불러온 뒤 eval 함수로 각 경우를 계산한다. (결과가 0일 경우만 출력)

▷ 참고 : [python] 파이썬 eval 함수 정리 및 예제

 

문제 출처 : https://www.acmicpc.net/problem/7490

7490번: 0 만들기