[파이썬] [백트래킹] 백준 7490 0 만들기

문제

https://www.acmicpc.net/problem/7490

7490번: 0 만들기

코드

t=int(input())

def cal(temp):
    #배열 맨뒤에 붙은 "+", "-". " "제거
    temp = temp[:-1]
    #정답을 위해 원본 저장
    ori=temp
    temp=temp.replace(" ","")
    #eval함수를 통해 string 수식 계산
    if eval(temp)==0:
        s.add(ori)


def dfs(index, temp):
    if index==len(array):
        cal(temp)
        return
    dfs(index+1,temp+str(array[index])+"+")
    dfs(index+1,temp+str(array[index])+"-")
    dfs(index+1,temp+str(array[index])+" ")


for _ in range(t):
    s=set()
    n=int(input())
    array=[]
    for i in range(n):
        array.append(i+1)
    dfs(0,"")
    #문제 조건인 ASCII 정렬을 위해 list로 변환
    result=list(s)
    result.sort()
    for i in result:
        print(i)
    print()

시간 복잡도

숫자 사이마다 ("+","-"," ")이 가능하므로 3**n