[BOJ] #7490 - 0 만들기

7490번: 0 만들기

 

** 문제 유형

• 재귀 호출, 완전 탐색

 

** 풀이

1. 자연수 N의 범위(3 <= N <= 9)가 매우 한정적이므로, 완전 탐색으로 문제 해결 가능
2. 수의 리스트와 연산자 리스트를 분리하여 모든 경우의 수를 계산 (재귀 함수 이용)
3. 파이썬의 eval() 함수를 이용하여 문자열 형태의 표현식을 계산

 

ex) n = 3 일 때,

수 리스트 = [1, 2, 3]

연산자 리스트 = [' ', '+', '-']

전체 경우의 수: 3^(n-1) = 3^2 = 9 (∵ 1, 2, 3 사이사이에 연산자가 들어가야 하므로)

 

import copy

def recursive(array, n): # 크기가 n인 모든 연산자 조합
    if len(array) == n: # n개가 채워지면
        operators_list.append(copy.deepcopy(array)) # array.pop()에 의해 빈 리스트가 되기 전에 copy
        return
    
    array.append(' ')
    recursive(array, n)
    array.pop()
    
    array.append('+')
    recursive(array, n)
    array.pop()
    
    array.append('-')
    recursive(array, n)
    array.pop()

---

tc = int(input())

for _ in range(tc):
    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()