[구현/백준] 7490번 : 0 만들기

- 문제 : https://www.acmicpc.net/problem/7490

 

문제 이해 

- 1부터 n까지의 수를 오름차순으로 정렬한 뒤 그 사이에 '+', '-', ' '(공백)의 연산을 넣은 뒤 연산의 결과가 0인 수식들을 출력하는 문제다. 

- 브루트포스 알고리즘으로 주어진 1 - n 숫자 사이에 계속 연산들을 넣고, 그 중 결과로 식별하면 된다고 이해까지는 했는데, 구체적으로 어떻게 구현해야할지 몰랐다. 

- 풀이를 찾아보니 일단 연산을 추가하는 거는 재귀함수로 돌리면 되고, 그렇게 구한 연산들을 숫자와 나란히 붙인뒤 값을 식별해 출력하면 된다.

    - 재귀함수 돌리고 목표 연산 개수인 k개에 도달하면, operator_list에 array를 deepcopy해서 추가해줘야 한다. (꼭 deepcopy를 해 야한다)

    - 연산 추가하는 순서도 중요하다 아스키 코드가 작은 ' ' (아스키 코드 34), '+' (아스키 코드 44), '-' (아스키 코드 45) 순서로 해야 틀리지 않는다. 

- 이때 만든 수식의 결과 값이 0인지 확인해야하는데, 문자열이므로 eval() 함수를 이용해 문자열을 계산해 결과가 0임을 확인하면된다. 여기에서 중요한 게 ' '(공백)은 count 되면 안되므로 ' '를 ''로 대체해서 eval을 진행하면 된다. 

 

근데 아직도 문제가 잘 이해 안 가는게 수식의 합이 0이어야 하는데, 아래 수식 같은 경우는 어떻게 결과가 0이 되는지 모르겠다,,,

1-2 3-4 5+6 7

그래서 pythontutor로 결과를 돌려봤는데  1-2(공백)3 인 경우에는 1-23으로 계산이 된다. 

 

 

정답 풀이 

import copy

def recursive(array, k):
    if len(array) == k:
        operator_list.append(copy.deepcopy(array))
        return
    
    array.append(' ')
    recursive(array, k)
    array.pop()
    
    array.append('+')
    recursive(array, k)
    array.pop()
    
    array.append('-')
    recursive(array, k)
    array.pop()
    
    
t = int(input())
for _ in range(t):
    n = int(input())
    operator_list = []
    recursive([], n - 1)
    integer = [i for i in range(1, n + 1)]
    
    for operator in operator_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()

 

참고 블로그 : https://reliablecho-programming.tistory.com/104