[백준] 7490번 : 0만들기

7490번: 0 만들기

해당 문제는 완전탐색문제로 해결할 수 있습니다. 각각의 숫자에 대하여 +, -, ‘ ‘ 연산을 수행해봄으로서

N이 9보다 작거나 같기 때문에 최악의 연산 횟수는 O(3^8) 입니다. 테스트 케이스 또한 10 이하 이기때문에

O(10* 3^8) 임으로 충분히 시간안에 풀 수 있습니다. 깊이우선 탐색으로 경우의 수를 모두 구한뒤 구한 결과를 0인지 아닌지에 따라서 결과를 출력 하면 됩니다.

oper = ['+', '-', ' ']
def dfs(depth, sequence):
    if depth == N:
        newsequence = sequence.replace(' ', '')
        total = eval(newsequence)
        if 0 == total:
            ans.append(sequence)
            return
        else:
            return

    for op in oper:
        newsequence = sequence + op + str(depth+1)
        dfs(depth+1,newsequence)

T = int(input())

for i in range(T):
    N = int(input())
    ans = []
    dfs(1, '1')
    ans.sort()
    for temp in ans:
        print(temp)
    if T-1 > i:
        print()