[백준] 7490. 0 만들기 (Python)

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

7490번: 0 만들기

 

📌 DFS로 +, -, 공백의 경우를 타고 들어가주었다.

📌 DFS 내부에서 계산 결과를 가지고 다녀보았는데, 생각처럼 계산 결과가 잘 나오지 않았다.

📌 따라서 마지막 숫자를 모두 사용했을 때, 만들어진 문자열을 eval 메소드를 통해 계산하고, 값이 0이면 res 리스트에 추가해주는 식으로 해결하였다.

📌 문자열 내부에서 공백을 사용한 경우를 대비해 replace 메소드로 공백을 없애준 후 eval 메소드를 사용하였다.

 

def DFS(nowNum, sentence):
    if nowNum == N+1:
        test = eval(sentence.replace(" ", ""))
        if test == 0:
            res.append(sentence)
    else:
        DFS(nowNum+1, sentence+'+'+str(nowNum))
        DFS(nowNum + 1, sentence + '-'+str(nowNum))
        DFS(nowNum + 1, sentence + ' '+str(nowNum))

T = int(input())

for _ in range(T):

    N = int(input())
    res = []
    DFS(2, "1")

    res.sort()

    for s in res:
        print(str(s))

    print()