[백준 7490] 0 만들기 (python 풀이)

1. 문제 

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

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

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

2. 입력

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

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

3. 출력

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

 

---

4. 포인트

1. 가지에서 가지로 뻗어난가는 경우의수를 담을때는 재귀함수를 사용하여 리스트에 원소를 추가해준다.
   
   • 만약 같은 리스트 메모리를 공유하는 방법이라면 최종적 값을 추가할때는 deepcopy를 사용해서 추가한다.
2.  eval 함수를 통해 string 형태의 식을 int 값과 쉽게 비교할 수 있다.

 

4. 문제 풀이

 경우의 수를 계산해보았을때 3**n 의 전체 식이 나오게되고 N은 9보다 작으므로 <19,683 의 경우의 수를 갖게된다.

시간 복잡도를 고려했을때 큰 수가 아니므로 전체 경우의 수를 모두 고려해서 풀면 된다.

 첫번째로 각 경우의 수(계산식) 에 대한 연산자를 리스트화 해야한다. 이는 재귀함수를 통해 구현할 수 있겠다. 리스트에 연산자 를 넣고  재귀적으로 함수를 호출하고 (가지에서 가지가 뻗어나감) 그리고 마지막으로 원소를 pop 해준다.  이렇게 순서대로 3가지 연산자에 대해 수행해주면된다. 그리고 중요한 부분은 최종적인 연산자리스트들를 담을 리스트에 해당 리스트를 deepcopy 해서 넣어준다. 그렇지 않으면 값들이 변해서 최종적으로 모두 같은 연산자리스트 만을 가지게 될 거이다.

 두번째로는 이렇게 만들어낸 연산자 리스트들에서 한개 그리고 integers 리스트에서 한개씩 빼서 리스트를 만들어 수식을 완성한다. 이렇게 얻어낸 값들을 string으로 만들고 eval 함수를 통해 0과 비교해서 출력하면되겠다.

 

# 주의할점은 문제에서 Ascii 순서에 따라 결과를 출력하라고 했으므로 반드시 " " , "+" , "-" 순서를 지켜서 리스트에 추가해야겠다.

 

# 0만들기
import copy

def make_operate_list(lst:list , n):
    if len(lst) == n:
        operators_list.append(copy.deepcopy(lst))
        return
    else:
        lst.append(" ")
        make_operate_list(lst , n)
        lst.pop()

        lst.append("+")
        make_operate_list(lst , n)
        lst.pop()
        
        lst.append("-")
        make_operate_list(lst ,n)
        lst.pop()
        
    
test = int(input())

for i in range(test):
    operators_list = []

    val = int(input())

    integers =[i for i in range(1 , val+1)]

    temp_operation_list = list()
    make_operate_list(temp_operation_list , val-1)

    for operators in operators_list:
        string = ""
        for i in range(val -1):
            string += str(integers[i]) + operators[i]
        string += str(integers[-1])
        if eval(string.replace(" ", "")) == 0:
            print(string)
    print()