[BOJ] 0 만들기(7490) 문제 풀기 | Python3

---

문제 풀이)

백트래킹으로 문제를 풀었다. depth를 인덱스 삼아 1,2,...,N까지 수를 수식에 더하며 dfs함수를 호출했다.

결과는 ASCII 순서로 출력해야하므로 dfs 함수 재귀호출 시 sorted(['+', '-', ' ']) 로 정렬한 순으로 기호를 덧붙였다. 

파이썬에는 eval() 이라는 강력한 함수가 존재하는데 공백 문자 그대로 입력하면 숫자가 붙여지지않고 에러를 내서 수식에 replace(' ', '') 한 결과를 eval 함수의 인자로 넘겼다. 

 

문제 코드)

 

def dfs(depth, exp):
    if depth==n:
        if eval(exp.replace(' ', ''))==0:
            print(exp)
        return
    for op in sorted(['+','-',' ']):
        dfs(depth+1, exp+op+string[depth])
        
for _ in range(int(input())):
    n=int(input())
    string=''.join(map(str, range(1,n+1)))
    dfs(1,'1')
    print()