[파이썬] [백트래킹] 백준 7490

쉬운 목차

문제

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

#7490: 0 생성

각 테스트 케이스에 대해 ASCII 순서로 0으로 이어지는 모든 표현식을 인쇄하십시오. 각 테스트 사례의 결과는 한 줄로 구분됩니다.

www.acmicpc.net

암호

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
    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