난이도

Gold 5

인증

문제

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

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

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

입력

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

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

출력

각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 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

해설 및 후기

직관적인 방식의 구현으로 이를 해결했다. dfs로 깊이를 높여가며 이를 수행하고, ascii별 우선순위를 주기 위해 ‘ ‘, ‘+’, ‘-‘ 순서로 다음 탐색을 정했다. 그리고 마지막 깊이까지 도달했을 때, 공백을 제외하고 eval하여 0이 나오는지를 확인했다. 그렇다면 해당 식을 출력했다.

굉장히 무식한 방법이지만, 자연수 n의 범위가 작아 가능한 방법이었던 것 같다.

제출 코드

n = int(input())

def solv(s):
    s=s.replace(' ','')
    return eval(s)

def dfs(num, depth, s, mx):
    if(depth == mx):
        if(solv(s) == 0):
            print(s)
        return
    
    dfs(num+1, depth+1, s+' '+str(num+1), mx)
    dfs(num+1, depth+1, s+'+'+str(num+1), mx)
    dfs(num+1, depth+1, s+'-'+str(num+1), mx)

def getNum(a):
    dfs(1,0,'1',int(a)-1)
    print()


for i in range(n):
    getNum(input())