7490(0 만들기) - 해결

0 만들기

 

문제

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

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

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

 

입력

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

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

 

출력

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

---

처음에는 순열을 사용하려 하렸지만 너무 시간이 오려걸려서 브루트포스를 사용하였다.

ASCII코드에 따라 ' ', '+', '-' 순으로 할 수 있는 조합을 다 돌면서 뽑아내는 방식을 사용하였다.

계산은 eval을 사용하였다.

import sys
input = sys.stdin.readline

T = int(input().strip())

def dfs(N):
    # 시작은 1에서 부터
    stack = [(1,[])]

    while stack:
        now, opers = stack.pop()
        next = now + 1
        # 현재 N이라면 끝
        if now == N:
            # 연산과 숫자를 합치기 위해서 뒤에 하나 더 붙이기
            oper_list = list(opers) + ['']
            # 합치기
            res = "".join(i + j for i, j in zip(num_list, oper_list))
            # 계산 띄어쓰기 부분은 붙이기
            if eval(res.replace(" ","")) == 0:
                # 0이라면 결과에 넣기
                results.append(res)
            # 계속 탐색
            continue

        # 차례대로 넣기
        for oper in oper_lists:
            if oper == " ":
                stack.append((next,opers + [oper]))
            elif oper == "-":
                stack.append((next,opers + [oper]))
            else:
                stack.append((next,opers + [oper]))
                
for tc in range(1,T+1):
    N = int(input().strip())
    # ASCII 코드 순으로 하기위해서 
    oper_lists = ['-','+',' ']
    # 쓰는 숫자들
    num_list = list(map(str,range(1,N+1)))
    # 결과들 저장
    results = []

    # N을 넘겨준다
    dfs(N)

    # 결과들 출력
    for i in results:
        print(i)
    # 띄어쓰기
    print()