[Python/파이썬] 백준 7490번 0 만들기

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

 

코드

ans = []


def bt(n, idx, exp):
    if idx == n:
        exp += str(idx)
        if eval(exp.replace(" ", '')) == 0:
            ans.append(exp)
        return
    for mid in ['+', '-', ' ']:
        bt(n, idx+1, exp+str(idx)+mid)


for _ in range(int(input())):
    n = int(input())
    ans = []    # 정답 배열 초기화
    bt(n, 1, "")
    ans.sort()  # ASCII 순서로 정렬
    for i in range(len(ans)):
        print(ans[i])
    print()

 

파이썬에서는 eval() 함수를 알면 이 문제를 쉽게 풀 수 있다.

eval() 함수는 인자로 받은 문자열 수식을 계산한 결과값을 리턴하는 함수이다. 그렇기 때문에 백트래킹 알고리즘을 사용하여 1~N까지의 수를 사용해서 만들 수 있는 수식을 만들고, 그 수식을 계산한 값이 0이라면 ans에 추가해주는 방식으로 풀었다. 그리고 ans 배열을 ASCII 순서로 정렬해야 하는데, 파이썬의 sort()가 정렬 기준으로 ASCII 사용하기 때문에 sort()를 사용한다면 쉽게 정렬할 수 있다.